Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium

2020-10-03 Thread Chris Belcher via bitcoin-dev
Hello list,

This email is an appendium or modification of the earlier CoinSwap
protocol published on this list. It is intended to fix the problems
found in review. (Original email quoted here too)


On 11/08/2020 13:05, Chris Belcher via bitcoin-dev wrote:
> I'm currently working on implementing CoinSwap (see my other email
> "Design for a CoinSwap implementation for massively improving Bitcoin
> privacy and fungibility").
> 
> CoinSwaps are special because they look just like regular bitcoin
> transactions, so they improve the privacy even for people who do not use
> them. Once CoinSwap is deployed, anyone attempting surveillance of
> bitcoin transactions will be forced to ask themselves the question: how
> do we know this transaction wasn't a CoinSwap?
> 
> This email contains a detailed design of the first protocol version. It
> makes use of the building blocks of multi-transaction CoinSwaps, routed
> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
> added later.
> 
> == Routed CoinSwap ==
> 
> Diagram of CoinSwaps in the route:
> 
> Alice > Bob > Charlie > Alice
> 
> Where (>) means one CoinSwap. Alice gives coins to Bob, who gives
> coins to Charlie, who gives coins to Alice. Alice is the market taker
> and she starts with the hash preimage. She chooses the CoinSwap amount
> and chooses who the makers will be.
> 
> This design has one market taker and two market makers in its route, but
> it can easily be extended to any number of makers.
> 
> == Multiple transactions ==
> 
> Each single CoinSwap is made up of multiple transactions to avoid amount
> correlation
> 
>   (a0 BTC) ---> (b0 BTC) ---> (c0 BTC) --->
> Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
>   (a2 BTC) ---> (b2 BTC) ---> (c2 BTC) --->
> 
> The arrow (--->) represent funding transactions. The money gets paid to
> a 2-of-2 multisig but after the CoinSwap protocol and private key
> handover is done they will be controlled by the next party in the route.
> 
> This example has 6 regular-sized transactions which use approximately
> the same amount of block space as a single JoinMarket coinjoin with 6
> parties (1 taker, 5 makers). Yet the privacy provided by this one
> CoinSwap would be far far greater. It would not have to be repeated in
> the way that Equal-Output CoinJoins must be.
> 
> == Direct connections to Alice ===
> 
> Only Alice, the taker, knows the entire route, Bob and Charlie just know
> their previous and next transactions. Bob and Charlie do not have direct
> connections with each other, only with Alice.
> 
> Diagram of Tor connections:
> 
> Bob  Charlie
>  |   /
>  |  /
>  | /
>   Alice
> 
> When Bob and Charlie communicate, they are actually sending and
> receiving messages via Alice who relays them to Charlie or Bob. This
> helps hide whether the previous or next counterparty in a CoinSwap route
> is a maker or taker.
> 
> This doesn't have security issues even in the final steps where private
> keys are handed over, because those private keys are always for 2-of-2
> multisig and so on their own are never enough to steal money.
> 
> 
> === Miner fees ===
> 
> Makers have no incentive to pay any miner fees. They only do
> transactions which earn them an income and are willing to wait a very
> long time for that to happen. By contrast takers want to create
> transactions far more urgently. In JoinMarket we coded a protocol where
> the maker could contribute to miner fees, but the market price offered
> of that trended towards zero. So the reality is that takers will pay all
> the miner fees. Also because makers don't know the taker's time
> preference they don't know how much they should pay in miner fees.
> 
> The taker will have to set limits on how large the maker's transactions
> are, otherwise makers could abuse this by having the taker consolidate
> maker's UTXOs for free.
> 
> == Funding transaction definitions ==
> 
> Funding transactions are those which pay into the 2-of-2 multisig addresses.
> 
> Definitions:
> I = initial coinswap amount sent by Alice = a0 + a1 + a2
> (WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
>respectively. Could be called "wallet Alice", "wallet
>Bob", etc
> (B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
> (M1, M2, M3) = Miner fees of the first, second, third, etc sets of
>funding transactions. Alice will choose wha

Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-09-03 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

On 03/09/2020 10:45, ZmnSCPxj wrote:
> Good morning Chris,
> 
>> A big downside is that it really ruins the property of allowing coins to
>> remain unspent indefinitely. That has privacy implications: if a coin
>> remains unspent for longer than 2 weeks (or another short locktime) then
>> for sure the transaction was not a CoinSwap, and so the anonymity set of
>> the CoinSwap system would be far smaller For this reason I'm pretty
>> desperate to solve the vulnerability without losing the coins remaining
>> unspent indefinitely feature.
> 
> Ah, right accept no small privacy leaks!

I'd argue its not even a small leak. A huge amount of coins remain
unspent for weeks, months and years, and it would be great to add them
to our CoinSwap anonymity set. And also have them benefit from
CoinSwap's anonymity set even if they didn't use CoinSwap.

> This seems a great solution!
> 
> Since B is the one offering HTLCs, the taker of a CoinSwap sequence can be B 
> as well.
> This means, the taker has to have *some* collateral input, of at least value 
> K, that it cannot swap (because if it tried to swap that amount, it would be 
> unable to provide a collateral as well).
> 
> How much does C need to know about the B collateralized contract transaction?
> At the minimum, it has to know the output pays out to the correct contract, 
> so it seems to me it has to know the entire B collateralized contract 
> transaction, meaning it learns another input of B ("collateral(B)") that is 
> not otherwise involved in the CoinSwap.
> This is important, again, if B is a taker, as it means an unrelated input of 
> B is now learned by C as having the same ownership as B.

Yes, in fact that's why in my example I talk about a CoinSwap between
two makers Bob and Charlie. Makers can be reasonably expected to own
multiple UTXOs, but takers cannot. As you say because collateral
payments breaks the ability of takers to sweep their entire wallet
through CoinSwap.

Happily, I think takers themselves don't need to use collateral
payments. Here's an argument to why:

Riskless theft attempts by the taker who no longer controls the coins
actually isnt riskless or costless: Because it reduces the privacy of
the previously-owned coins. If a taker genuinely wanted good privacy
(Which, after all, they're paying for via miner fees and CoinSwap fees)
then they would benefit if the coins they no longer own remain unspent
for a long time, because it increases their anonymity set by making them
hide among a greater crowd of coins which also don't get spent for a
long time.
Assuming that all peers, especially makers, deploy multiple redundant
watchtowers then we can assume the success rate of such a theft attempt
is very low. Because of the very low payoff, and privacy benefit of
leaving coins unspent, then it can be argued that taker software which
attempts such theft will never get popular.

Of course this privacy argument only applies to takers, and if the
CoinSwap contract is between two makers as part of a multi-transaction
CoinSwap then it doesn't apply. So a maker-to-maker CoinSwap must use
collateral payments.

== Leak of first hop ==
Collateral inputs only applying to maker-maker CoinSwaps adds an
additional information leak, which is that makers can now tell whether
their previous peer was a taker or maker, based on whether they used a
collateral input or not.

This should be okay because the first maker doesn't know the final
destination of the coins. This is similar to Tor, where this information
is already leaked, for example when the user connects to a Tor bridge.
The operator of the Tor bridge knows that everyone connecting to it is
not a Tor relay node but an actual user. The operator of the tor bridge
still has no idea where the user's internet traffic goes. Our situation
is actually better than Tor, because in Tor the final relay always knows
that they are an exit node, while the final maker in a CoinSwap might
not know that.

Also, if the taker does happen to own an extra UTXO, they may choose to
use a collateral input anyway, just to pretend that they're a maker.


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


Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-09-03 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,


On 25/08/2020 04:16, ZmnSCPxj wrote:
> 
> Good morning Antoine,
> 
> 
>> Note, I think this is independent of picking up either relative or absolute 
>> timelocks as what matters is the block delta between two links.
> 
> I believe it is quite dependent on relative locktimes.
> Relative locktimes *require* a contract transaction to kick off the relative 
> locktime period.
> On the other hand, with Scriptless Script (which we know how to do with 
> 2p-ECDSA only, i.e. doable pre-Taproot), absolute locktimes do not need a 
> contract transaction.
> 
> With absolute locktimes + Scriptless SCript, in a single onchain PTLC, one 
> participant holds a completely-signed timelock transaction while the other 
> participant holds a completely-signed pointlock transaction.
> This can be arranged by having one side offer partial signatures for the 
> transaction of the other, and once completing the signature, not sharing it 
> with the other until we are ready to actually broadcast the transaction of 
> our own volition.
> There is no transaction that both participants hold in completely-signed form.
> 
> This should remove most of the shenanigans possible, and makes the 30xRBF 
> safe for any range of fees.
> I think.
> 
> Since for each PTLC a participant holds only its "own" transaction, it is 
> possible for a participant to define its range of fees for the RBF versions 
> of the transaction it owns, without negotiation with the other participant.
> Since the fee involved is deducted from its own transaction, each participant 
> can define this range of RBFed fees and impose it on the partial signatures 
> it gets from the other participant.
> 
> --
> 
> Private key turnover is still useful even in an absolute-timelock world.
> 
> If we need to bump up the block delta between links, it might be impractical 
> to have the total delta of a multi-hop swap be too long at the taker.
> 
> As a concrete example, suppose A is a taker who wants to route over makers B 
> and C.
> However, B and C require a CLTV delta of 1 week.
> 
> If A wants to route "directly" A->B->C->A, then if something bad happens, it 
> could be looking at having its funds locked for two weeks.
> 
> To reduce this risk, A can instead first swap A->B->A, then when that 
> completes, A->C->A.
> This limits its funding lockup to 1 week.
> 
> Private key turnover is useful since as soon as the A->B->A swap completes, 
> it can directly fund the A->C->A swap from the B-side funding transaction of 
> the A->B->A swap.
> 
>  |   A->B->A |A->C->A   |
>  :   :  :
>   A -:->funding A> B :  :
>  :   :  :
>   B -:->funding A -:--> funding A --> C :
>  :   :  :
>  :   :C-> funding A --:-> to-cold  A -->
>  :   :  :
> 
> This increases the number of transactions by 1 per swap beyond the first, 
> compared to a direct routing A->B->C->A, but this may be worth it for A if 
> the timelocks involved are too big for A.
> 
> With 2p-ECDSA, a funding A looks exactly the same as a to-cold A, so B is 
> unable to reliably determine if it is the last hop in the route.
> 
> Without private key turnover, A would have:
> 
>   **NO** private key turnover!
> 
>  |   A->B->A |A->C->A  |
>  :   : :
>   A -:->funding A> B : :
>  :   : :
>   B -:->funding A -:--> claim A -> funding A --> C :
>  :   : :
>  :   :   C-> funding A --:-> to-cold  A 
> -->
>  :   : :
> 
> So if timelock-deltas are possibly-high (to reduce the probability of the 
> MAD-HTLC argument, and other attacks, succeeding), takers might prefer to 
> route by completing one swap first before starting the next one, and private 
> key turnover is useful by reducing blockspace required by each hop.
> 
> For reference, this is how it looks like with a single A->B->C->A swap with 
> private key turnover:
> 
>  |   A->B->C->A  |
>  :   :
>   A -:->funding A> B :
>  :   :
>   B -:->funding B -> C :
>  :   :
>   C -:->funding A -:-> to-cold A -->
>  :   :
> 
> This is still smaller than in the A->B->A, A->C->A with private key turnover, 
> by one funding tx per hop.
> However, A risks a much higher timelock (twice the timelock).
> Thus, A might prefer a lower timelock in exchange for paying for an 
> additional transaction.
> 
> Regards,
> ZmnSCPxj
> 


Separating 

Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-08-29 Thread Chris Belcher via bitcoin-dev
ng the contract transaction to one and only one version
> would overcome this attack. A honest intermediate hop, as soon as seeing a
> relative timelock triggered backward would immediately broadcast the
> outgoing link contract tx or if it's already in network mempools broadcast
> a higher-feerate child. As you don't have valid multiple contract
> transactions, an attacker can't obstruct you to propagate the correct
> child, as you are not blind about the parent txid.
> 
> Lastly, one downside of using relative timelocks, in case of one downstream
> link failure, it forces every other upstream hops to go onchain to protect
> against this kind of pinning scenario. And this would be a privacy
> breakdown, as a maker would be able to provoke one, thus constraining every
> upstream hops to go onchain with the same hash and revealing the CoinSwap
> route.
> 
> Let me know if I reviewed the correct transactions circuit model or
> misunderstood associated semantic. I might be completely wrong, coming from
> a LN perspective.
> 
> Cheers,
> Antoine
> 
> Le mar. 11 août 2020 à 13:06, Chris Belcher via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> a écrit :
> 
>> I'm currently working on implementing CoinSwap (see my other email
>> "Design for a CoinSwap implementation for massively improving Bitcoin
>> privacy and fungibility").
>>
>> CoinSwaps are special because they look just like regular bitcoin
>> transactions, so they improve the privacy even for people who do not use
>> them. Once CoinSwap is deployed, anyone attempting surveillance of
>> bitcoin transactions will be forced to ask themselves the question: how
>> do we know this transaction wasn't a CoinSwap?
>>
>> This email contains a detailed design of the first protocol version. It
>> makes use of the building blocks of multi-transaction CoinSwaps, routed
>> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
>> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
>> added later.
>>
>> == Routed CoinSwap ==
>>
>> Diagram of CoinSwaps in the route:
>>
>> Alice > Bob > Charlie > Alice
>>
>> Where (>) means one CoinSwap. Alice gives coins to Bob, who gives
>> coins to Charlie, who gives coins to Alice. Alice is the market taker
>> and she starts with the hash preimage. She chooses the CoinSwap amount
>> and chooses who the makers will be.
>>
>> This design has one market taker and two market makers in its route, but
>> it can easily be extended to any number of makers.
>>
>> == Multiple transactions ==
>>
>> Each single CoinSwap is made up of multiple transactions to avoid amount
>> correlation
>>
>>   (a0 BTC) ---> (b0 BTC) ---> (c0 BTC) --->
>> Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
>>   (a2 BTC) ---> (b2 BTC) ---> (c2 BTC) --->
>>
>> The arrow (--->) represent funding transactions. The money gets paid to
>> a 2-of-2 multisig but after the CoinSwap protocol and private key
>> handover is done they will be controlled by the next party in the route.
>>
>> This example has 6 regular-sized transactions which use approximately
>> the same amount of block space as a single JoinMarket coinjoin with 6
>> parties (1 taker, 5 makers). Yet the privacy provided by this one
>> CoinSwap would be far far greater. It would not have to be repeated in
>> the way that Equal-Output CoinJoins must be.
>>
>> == Direct connections to Alice ===
>>
>> Only Alice, the taker, knows the entire route, Bob and Charlie just know
>> their previous and next transactions. Bob and Charlie do not have direct
>> connections with each other, only with Alice.
>>
>> Diagram of Tor connections:
>>
>> Bob  Charlie
>>  |   /
>>  |  /
>>  | /
>>   Alice
>>
>> When Bob and Charlie communicate, they are actually sending and
>> receiving messages via Alice who relays them to Charlie or Bob. This
>> helps hide whether the previous or next counterparty in a CoinSwap route
>> is a maker or taker.
>>
>> This doesn't have security issues even in the final steps where private
>> keys are handed over, because those private keys are always for 2-of-2
>> multisig and so on their own are never enough to steal money.
>>
>>
>> === Miner fees ===
>>
>> Makers have no incentive to pay any miner fees. They only do
>> transactions which earn them an income and are willi

Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-08-21 Thread Chris Belcher via bitcoin-dev
Hello,

On 21/08/2020 05:20, ZmnSCPxj wrote:
> Good morning,
> 
> 
> 
>> Right, so if the taker uses only a single maker then they must have more
>> than one UTXO.
> 
> Spending one UTXO is fine, it is generating a transaction that has one output 
> that is problematic.
> 
> What needs to happen is that this single UTXO is spent to two outputs: the 
> CoinSwap 2-of-2 and the change output.
> This is because intermediate makers will have very high likelihood of 
> generating such a pattern (it is unlikely they have an exact amount that a 
> taker would require of them), and the occassional maker might have a very 
> large UTXO that it can use for similar purposes.
> 
> One thing a taker can do would be to multipath its CoinSwap, i.e. it spends 
> any number of UTXOs and creates two outputs, which are actually two separate 
> CoinSwap 2-of-2s to different makers.
> As each maker is unaware of the other, this should be similar to the case 
> where the maker is an intermediate hop and is getting its incoming HTLC from 
> another maker, which is unlikely to have a precise amount and will thus have 
> a transaction that has two outputs, the 2-of-2 CoinSwap and the change.

Agreed.
I write about multipath CoinSwap routes in the original design document,
under "Combining multi-transaction with routing"


 === Miner fees ===
 Makers have no incentive to pay any miner fees. They only do
 transactions which earn them an income and are willing to wait a very
 long time for that to happen. By contrast takers want to create
 transactions far more urgently. In JoinMarket we coded a protocol where
 the maker could contribute to miner fees, but the market price offered
 of that trended towards zero. So the reality is that takers will pay all
 the miner fees. Also because makers don't know the taker's time
 preference they don't know how much they should pay in miner fees.
 The taker will have to set limits on how large the maker's transactions
 are, otherwise makers could abuse this by having the taker consolidate
 maker's UTXOs for free.
>>>
>>> Why not have the taker pay for the first maker-spent UTXO and have 
>>> additional maker-spent UTXOs paid for by the maker?
>>> i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4 
>>> BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
>>> Disagreements on feerate can be resolved by having the taker set the 
>>> feerate, i.e. "the customer is always right".
>>> Thus if the maker has to spend two UTXOs to make up the 0.4 BTC bag, it 
>>> pays for the mining fees for that extra UTXO.
>>> The maker can always reject the swap attempt if it has to spend multiple 
>>> UTXOs and would lose money doing so if the taker demands a too-high feerate.
>>
>> Having the taker pay for just one UTXO will have an unfortunate side
>> effect of resulting in the maker's money being split up into a large
>> number of UTXOs, because every CoinSwap they take part in has an
>> incentive to increase their UTXO count by one. At the start of
>> JoinMarket this was an issue where then a taker wanting to CoinJoin a
>> large would come along and the result would be a huge CoinJoin
>> transaction with many many small inputs. Perhaps the taker could pay for
>> 2-3 UTXOs to counteract this. (Of course the exact number would be
>> configurable by the taker user, but defaults usually don't get changed).
>>
>> I'm still not convinced with having makers contribute to miner fees. In
>> JoinMarket we tried to get makers to contribute a little to miner fees
>> and simply they never did in any meaningful way. The market has spoken.
>> In terms of incentives makers are happy to wait a very long time, if we
>> assume they're just HODLers then even if they earn a few thousand
>> satoshis that's good.
>>
 == Contract transaction definitions ==
 Contract transactions are those which may spend from the 2-of-2 multisig
 outputs, they transfer the coins into a contract where the coins can be
 spent either by waiting for a timeout or providing a hash preimage
 value. Ideally contract transactions will never be broadcast but their
 existence keeps all parties honest.
 M~ is miner fees, which we treat as a random variable, and ultimately
 set by whichever pre-signed RBF tx get mined. When we talk about the
 contract tx, we actually mean perhaps 20-30 transactions which only
 differ by the miner fee and have RBF enabled, so they can be broadcasted
 in sequence to get the contract transaction mined regardless of the
 demand for block space.
>>>
>>> The highest-fee version could have, in addition, CPFP-anchor outputs, like 
>>> those being proposed in Lightning, so even if onchain fees rise above the 
>>> largest fee reservation, it is possible to add even more fees.
>>> Or not.
>>> Hmm.
>>
>> I think RBF transactions are better because they ultimately use less
>> block space than CPFP.
>>
>> There 

Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-08-20 Thread Chris Belcher via bitcoin-dev
Hello Nadav and ZmnSCPxj,

On 20/08/2020 22:38, ZmnSCPxj wrote:
> Good morning Nadav,
> 
>> Hey Chris and all,
>>
>> Looking good :) I have one major concern though
>>
>>>     q = EC privkey generated by maker
>>>     Q = q.G = EC pubkey published by maker
>>>
>>>     p = nonce generated by taker
>>>     P = p.G = nonce point calculated by taker
>>>
>>>     R = Q + P = pubkey used in bitcoin transaction
>>>       = (q + p).G
>>
>> If I'm understanding this correctly (which I'm not sure I ame), it seems 
>> like the plan is to put R on-chain as the key to an output? As stated this 
>> is completely insecure as Q is known in advance so the taker can always 
>> choose a nonce p but then claim that their nonce point is p.G - Q so that 
>> the key that goes on-chain is (p.G - Q + Q) = p.G allowing them to steal the 
>> funds.
> 
> My reading from this is that nonce `p` has to be given by the taker to the 
> maker outright.
> In original post:
> 
>> Taker sends unsigned transaction which pays to multisig using pubkey Q,
>> and also sends nonce p.
> 
> Thus, taker provides a proof-of-knowledge, i.e. the actual `p` scalar itself 
> (not zero-knowledge, but what the maker needs is proof-of-knowledge, and 
> could not care less if the proof is zero-knowledge or not).

Yes this looks right. In hindsight my text could be clarified by
changing the relevant lines to:

p = nonce generated by taker, sent to maker
P = p.G = nonce point calculated by taker

R = Q + P = pubkey used in bitcoin transaction, calculated by taker
  = (q + p).G = same pubkey, calculated by maker


I don't think the key subtraction attack described by Nadav will work
here...?


> On the other hand, I do not see the point of this tweak if you are going to 
> use 2p-ECDSA, since my knowledge is that 2p-ECDSA uses the pubkey that is 
> homomorphic to the product of the private keys.
> And that pubkey is already tweaked, by the fresh privkey of the maker (and 
> the maker is buying privacy and wants security of the swap, so is 
> incentivized to generate high-entropy temporary privkeys for the actual swap 
> operation).
> 
> Not using 2p-ECDSA of some kind would remove most of the privacy advantages 
> of CoinSwap.
> You cannot hide among `2   2 OP_CHECKMULTISIG` scripts of Lightning, 
> because:
> 
> * Lightning channel closes tend to be weeks at least after the funding 
> outpoint creation, whereas CoinSwap envisions hours or days.
> * Lightning mutual channel closes have a very high probability of spending to 
> two P2WPKH addresses.
> 
> You need to hide among the much larger singlesig anonymity set, which means 
> using a single signature (created multiparty by both participants), not two 
> signatures (one from each participant).
> 
> Or is this intended for HTLCs in open-coded SCRIPTs `OP_DUP OP_IF OP_HASH160 
>  OP_EQUAL  OP_ELSE  OP_CHECKSEQUENCEVERIFY OP_DROP  
> OP_ENDIF OP_CHECKSIG`?
> This provides a slight privacy boost in a case (contract transaction 
> publication) where most of the privacy is lost anyway.

I completely agree that 2of2 multisigs made with OP_CHECKMULTISIG are
lacking in terms of privacy, and that 2p-ECDSA is much better. However
this whole protocol is quite complicated and I thought it would be a
good move to first implement it with OP_CHECKMULTISIG, to get all the
other details right (miner fees, coinswap fees, private key handover,
contract transactions, tor hidden services, watchtowers, etc etc) and
then add 2p-ECDSA later. Of course in that case all this tweaking of
public keys would be superseded by the 2p-ECDSA protocol.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-08-20 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

Thanks for the review. My comments are inline.

On 20/08/2020 12:17, ZmnSCPxj wrote:
> Good morning Chris,
> 
> Great to see this!
> 
> Mostly minor comments.
> 
> 
> 
>>
>> == Direct connections to Alice ===
>>
>> Only Alice, the taker, knows the entire route, Bob and Charlie just know
>> their previous and next transactions. Bob and Charlie do not have direct
>> connections with each other, only with Alice.
>>
>> Diagram of Tor connections:
>>
>> Bob Charlie
>> | /
>> | /
>> | /
>> Alice
>>
>> When Bob and Charlie communicate, they are actually sending and
>> receiving messages via Alice who relays them to Charlie or Bob. This
>> helps hide whether the previous or next counterparty in a CoinSwap route
>> is a maker or taker.
>>
>> This doesn't have security issues even in the final steps where private
>> keys are handed over, because those private keys are always for 2-of-2
>> multisig and so on their own are never enough to steal money.
> 
> This has a massive advantage over CoinJoin.
> 
> In CoinJoin, since all participants sign a single transaction, every 
> participant knows the total number of participants.
> Thus, in CoinJoin, it is fairly useless to have just one taker and one maker, 
> the maker knows exactly which output belongs to the taker.
> Even if all communications were done via the single paying taker, the 
> maker(s) are shown the final transaction and thus can easily know how many 
> participants there are (by counting the number of equal-valued outputs).
> 
> With CoinSwap, in principle no maker has to know how many other makers are in 
> the swap.
> 
> Thus it would still be useful to make a single-maker CoinSwap, as that would 
> be difficult, for the maker, to diferentiate from a multi-maker CoinSwap.

Yes great point.

> There are still a few potential leaks though:
> 
> * If paying through a CoinSwap, the cheapest option for the taker would be to 
> send out a single large UTXO (single-output txes) to the first maker, and 
> then demand the final payment and any change as two separate swaps from the 
> final maker.
>   * Intermediate makers are likely to not have exact amounts, thus is 
> unlikely to create a single-output tx when forwarding.
>   * Thus, the first maker could identify the taker.

Right, so if the taker uses only a single maker then they must have more
than one UTXO.

This leak in the case of a taker spending a single UTXO also happens
when the taker needs to create a branching route. I described this in my
original email "Design for a CoinSwap implementation for massively
improving Bitcoin privacy and fungibility" under the section "Combining
multi-transaction with routing" (the second diagram).

I think this might be unavoidable. If the taker has just one UTXO they'd
be much better off using multiple makers for this reason.


> * The makers can try timing the communications lag with the taker.
>   The general assumption would be that more makers == more delay in taker 
> responses.

Sounds like adding random delays would fix this. The protocol already
involves waiting for a confirmation (average waiting time 10 minutes, at
best) and might involve more confirmations for extra security and
privacy. So adding a random delay of up to 0.5-1 minutes shouldnt cause
too many issues.
Also the Tor network can be pretty laggy so that might add enough noise
anyway.

>>
>> === Miner fees ===
>>
>> Makers have no incentive to pay any miner fees. They only do
>> transactions which earn them an income and are willing to wait a very
>> long time for that to happen. By contrast takers want to create
>> transactions far more urgently. In JoinMarket we coded a protocol where
>> the maker could contribute to miner fees, but the market price offered
>> of that trended towards zero. So the reality is that takers will pay all
>> the miner fees. Also because makers don't know the taker's time
>> preference they don't know how much they should pay in miner fees.
>>
>> The taker will have to set limits on how large the maker's transactions
>> are, otherwise makers could abuse this by having the taker consolidate
>> maker's UTXOs for free.
> 
> Why not have the taker pay for the *first* maker-spent UTXO and have 
> additional maker-spent UTXOs paid for by the maker?
> i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4 BTC", 
> and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
> 
> Disagreements on feerate can be resolved by having the taker set the feerate, 
> i.e. "the customer is always right".
> Thus if the maker *has to* spend two UTXOs to make up the 0.4 BTC bag, it 
> pays for the mining fees for that extra UTXO.
> The maker can always reject the swap attempt if it *has to* spend multiple 
> UTXOs and would lose money doing so if the taker demands a too-high feerate.

Having the taker pay for just one UTXO will have an unfortunate side
effect of resulting in the maker's money being split up into a large
number of UTXOs, because 

[bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap

2020-08-11 Thread Chris Belcher via bitcoin-dev
I'm currently working on implementing CoinSwap (see my other email
"Design for a CoinSwap implementation for massively improving Bitcoin
privacy and fungibility").

CoinSwaps are special because they look just like regular bitcoin
transactions, so they improve the privacy even for people who do not use
them. Once CoinSwap is deployed, anyone attempting surveillance of
bitcoin transactions will be forced to ask themselves the question: how
do we know this transaction wasn't a CoinSwap?

This email contains a detailed design of the first protocol version. It
makes use of the building blocks of multi-transaction CoinSwaps, routed
CoinSwaps, liquidity market, private key handover, and fidelity bonds.
It does not include PayJoin-with-CoinSwap, but that's in the plan to be
added later.

== Routed CoinSwap ==

Diagram of CoinSwaps in the route:

Alice > Bob > Charlie > Alice

Where (>) means one CoinSwap. Alice gives coins to Bob, who gives
coins to Charlie, who gives coins to Alice. Alice is the market taker
and she starts with the hash preimage. She chooses the CoinSwap amount
and chooses who the makers will be.

This design has one market taker and two market makers in its route, but
it can easily be extended to any number of makers.

== Multiple transactions ==

Each single CoinSwap is made up of multiple transactions to avoid amount
correlation

  (a0 BTC) ---> (b0 BTC) ---> (c0 BTC) --->
Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
  (a2 BTC) ---> (b2 BTC) ---> (c2 BTC) --->

The arrow (--->) represent funding transactions. The money gets paid to
a 2-of-2 multisig but after the CoinSwap protocol and private key
handover is done they will be controlled by the next party in the route.

This example has 6 regular-sized transactions which use approximately
the same amount of block space as a single JoinMarket coinjoin with 6
parties (1 taker, 5 makers). Yet the privacy provided by this one
CoinSwap would be far far greater. It would not have to be repeated in
the way that Equal-Output CoinJoins must be.

== Direct connections to Alice ===

Only Alice, the taker, knows the entire route, Bob and Charlie just know
their previous and next transactions. Bob and Charlie do not have direct
connections with each other, only with Alice.

Diagram of Tor connections:

Bob  Charlie
 |   /
 |  /
 | /
  Alice

When Bob and Charlie communicate, they are actually sending and
receiving messages via Alice who relays them to Charlie or Bob. This
helps hide whether the previous or next counterparty in a CoinSwap route
is a maker or taker.

This doesn't have security issues even in the final steps where private
keys are handed over, because those private keys are always for 2-of-2
multisig and so on their own are never enough to steal money.


=== Miner fees ===

Makers have no incentive to pay any miner fees. They only do
transactions which earn them an income and are willing to wait a very
long time for that to happen. By contrast takers want to create
transactions far more urgently. In JoinMarket we coded a protocol where
the maker could contribute to miner fees, but the market price offered
of that trended towards zero. So the reality is that takers will pay all
the miner fees. Also because makers don't know the taker's time
preference they don't know how much they should pay in miner fees.

The taker will have to set limits on how large the maker's transactions
are, otherwise makers could abuse this by having the taker consolidate
maker's UTXOs for free.

== Funding transaction definitions ==

Funding transactions are those which pay into the 2-of-2 multisig addresses.

Definitions:
I = initial coinswap amount sent by Alice = a0 + a1 + a2
(WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
   respectively. Could be called "wallet Alice", "wallet
   Bob", etc
(B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
(M1, M2, M3) = Miner fees of the first, second, third, etc sets of
   funding transactions. Alice will choose what these are
   since she's paying.
multisig(A+B) = A 2of2 multisig output with private keys held by A and B

The value in square parentheses refers to the bitcoin amount.

Alice funding txes
  [WA btc] ---> multisig (Alice+Bob) [I btc]
change [WA-M1-I btc]
Bob funding txes
  [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
change [WB-I+B btc]
Charlie funding txes
  [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
change [WC-(I-M2-B)+C btc]

Here we've drawn these transactions as single transactions, but they are
actually multiple transactions where the outputs add up some value (e.g.
add up to I in Alice's transactions.)

=== Table of balances before and after a successful CoinSwap ===

If a CoinSwap is successful then all the multisig outputs in the 

Re: [bitcoin-dev] Hiding CoinSwap Makers Among Custodial Services

2020-06-13 Thread Chris Belcher via bitcoin-dev
On 13/06/2020 15:06, ZmnSCPxj wrote:
> Good morning Chris,
> 
>>
>> Would it be fair to summarize the idea in this way:
>>
>> CoinSwappers can slow down the CoinSwap process which will give an
>> opportunity for makers to use batching.
> 
> I think so.
> 
> Regards,
> ZmnSCPxj
> 

It's definitely a good idea. As well as improving privacy by pretending
to be a service provider which uses batching, it may also be practical
just because CoinSwap takers will want to slow down the process for
greater privacy so that an adversary would have to search more of the
blockchain to attempt to deanonymize them. Also, by being prepared to
wait longer the takers will also save miner fees.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Hiding CoinSwap Makers Among Custodial Services

2020-06-13 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

On 11/06/2020 12:51, ZmnSCPxj wrote:
> Good morning Chris, and bitcoin-dev (but mostly Chris),
> 
> 
> I made a random comment regarding taint on bitcoin-dev recently: 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017961.html
> 
>> For CoinSwap as well, we can consider that a CoinSwap server could make 
>> multiple CoinSwaps with various clients.
>> This leads to the CoinSwap server owning many small UTXOs, which it at some 
>> point aggregates into a large UTXO that it then uses to service more clients 
>> (for example, it serves many small clients, then has to serve a single large 
>> client that wants a single large UTXO for its own purposes).
>> This aggregation again leads to spreading of taint.
> 
> I want to propose some particular behaviors a SwapMarket maker can engage in, 
> to improve the privacy of its customers.
> 
> Let us suppose that individual swaps use some variant of Succinct Atomic Swap.
> Takers take on the role of Alice in the SAS description, makers take on the 
> role of Bob.
> We may be able to tweak the SAS protocol or some of its parameters for our 
> purposes.
> 
> Now, what we will do is to have the maker operate in rounds.
> 
> Suppose two takers, T1 and T2, contact the sole maker M in its first ever 
> round.
> T1 and T2 have some coins they want to swap.
> They arrange things all the way to confirmation of the Alice-side funding tx, 
> and pause just before Bob creates its own funding tx for their individual 
> swaps.
> The chain now shows these txes/UTXOs:
> 
>  42 of T1 --->  42 of T1 & M
>  50 of T2 --->  50 of T2 & M
> 100 of T1 ---> 100 of T1 & M
> 
> 200 of M  -
> 
> Now the entire point of operating in rounds is precisely so that M can 
> service multiple clients at the same time with a single transaction, i.e. 
> batching.
> So now M provides its B-side tx and complete the SAS protocols with each of 
> the takers.
> SAS gives unilateral control of the outputs directly to the takers, so we 
> elide the fact that they are really 2-of-2s below:
> 
>  42 of T1 --->  42 of T1 & M
>  50 of T2 --->  50 of T2 & M
> 100 of T1 ---> 100 of T1 & M
> 
> 200 of M  +-->  11 of M
>   +--> 140 of T1
>   +-->  49 of T2
> 
> (M extracted 1 unit from each incoming coin as fee; they also live in a 
> fictional universe where miners mine transactions out of the goodness of 
> their hearts.)
> Now in fact the previous transactions are, after the SAS, solely owned by M 
> the maker.
> Now suppose on the next round, we have 3 new takers, T3, T4, and T5, who 
> offer some coins to M to CoinSwap, leading to more blockchain data:
> 
>  42 of T1 --->  42 of T1 & M
>  50 of T2 --->  50 of T2 & M
> 100 of T1 ---> 100 of T1 & M
> 
> 200 of M  -+->  11 of M
>+-> 140 of T1
>+->  49 of T2
> 
>  22 of T3 --->  22 of T3 & M
>  90 of T3 --->  90 of T3 & M
>  11 of T4 --->  11 of T4 & M
>  50 of T4 --->  50 of T4 & M
>  20 of T5 --->  20 of T5 & M
> 
> In order to service all the new takers of this round, M takes the coins that 
> it got from T1 and T2, and uses them to fund a new combined CoinSwap tx:
> 
>  42 of T1 --->  42 of T1 & M -+--+-> 110 of T3
>  50 of T2 --->  50 of T2 & M -+  +->  59 of T4
> 100 of T1 ---> 100 of T1 & M -+  +->  14 of T5
>  +->   9 of M
> 200 of M  -+->  11 of M
>+-> 140 of T1
>+->  49 of T2
> 
>  22 of T3 --->  22 of T3 & M
>  90 of T3 --->  90 of T3 & M
>  11 of T4 --->  11 of T4 & M
>  50 of T4 --->  50 of T4 & M
>  15 of T5 --->  15 of T5 & M
> 
> That transaction, we can observe, looks very much like a batched transaction 
> that a custodial service might produce.
> 
> Now imagine more rounds, and I think you can begin to imagine that the magic 
> of transaction batching, ported into SwapMarket, would help mitigate the 
> blockchain size issues that CoinSwap has.
> 
> Makers are expected to adopt this technique as this reduces the overall cost 
> of transactions they produce, thus they are incentivized to use this 
> technique to increase their profitability.
> 
> At the same time, it spreads taint around and increases the effort that chain 
> analysis must go through to identify what really happened.
> 
> Regards,
> ZmnSCPxj
> 

Would it be fair to summarize the idea in this way:

CoinSwappers can slow down the CoinSwap process which will give an
opportunity for makers to use batching.

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


Re: [bitcoin-dev] Tainting, CoinJoin, PayJoin, CoinSwap

2020-06-10 Thread Chris Belcher via bitcoin-dev
Hello nopara73,

On 10/06/2020 13:32, nopara73 via bitcoin-dev wrote:
> The problem with CoinJoins is that desire for privacy is explicitly
> signalled by them, so adversaries can consider them "suspicious." PayJoin
> and CoinSwap solve this problem, because they are unnoticeable. I think
> this logic doesn't stand for scrutiny.
> 
>>From here on let's use the terminology of a typical adversary: there are 3
> kinds of coin histories: "clean", "dirty" and "suspicious".
> The aftermath of you using a "dirty" coin is knocks on your door. You using
> a "suspicious" coin is uncomfortable questions and you using a "clean" coin
> is seamless transfer.
> 
> In scenario 1, you start out with a "clean" history. By using CoinJoins you
> make your new coin's history "suspicious" so you have no incentive to
> CoinJoin. By using CoinSwap/PayJoin your new coin can be either "clean" or
> "dirty". What would a "clean" coin owner prefer more? Take the risk of
> knocking on the door or answering uncomfortable questions?
> 
> In scenario 2, you start out with a "dirty" history. By using CoinJoins you
> make your new coin's history "suspicious" so you have an incentive to
> CoinJoin. By using CoinSwap/PayJoin your new coin can either be "clean" or
> "dirty". What would a "dirty" coin owner prefer more? And here's an
> insight: you may get knocks on your door for a dirty coin that you have
> nothing to do with. And you can prove this fact to the adversary, but by
> doing so, you'll also expose that you started out with a "dirty" coin to
> begin with and now the adversary becomes interested in you for a different
> reason.
> 
> You can also examine things assuming full adoption of PJ/CS vs full
> adoption of CJ, but you'll see that full adoption of any of these solves
> the tainting issue.
> 
> So my current conclusion is that PJ/CS does not only not solve the taint
> problem, it just alters it and ultimately very similar problems arise for
> the users. Maybe the goal of unobservable privacy is a fallacy in this
> context as it is based on the assumption that desiring privacy is
> suspicious, so you want to hide the fact that you desire privacy. And the
> solution to the taint issue is either protocol change or social change
> (decent adoption.)
> 
> PS.: Please try to keep the conversation to the Taint Issue as this email
> of mine isn't supposed to be discussing general pros and cons of various
> privacy techniques.
> 
> Any thoughts?
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

There are two concepts here: Taint analysis and the detectableness of
privacy protocols.

Taint analysis is quite an old technique, I remember seeing the
blockchain.info explorer having a tool for calculating a value for taint
back in 2013, long before any widely-used CoinJoin implementations were
created. I think taint was first created to attack the privacy technique
of simply sending coins to yourself multiple times. If those coins were
for example stolen from an exchange's hot wallet then the taint between
the exchange addresses and the later addresses would still be 100% even
if the thief sent the coins to himself multiple times.

A very important point is that it's difficult to reason about taint
analysis algorithms because they are often hypothetical, likely
closed-source, not available to the public for review and changing all
the time. OP talks about the three categories "clean", "dirty" and
"suspicious" which is one possibility. I've read about other taint
analysis algorithms which result in a numerical score out of 100.
Blockchain.info's algorithm calculated taint as a number expressing the
relation between any two addresses, so it wouldn't make sense to say "an
address" is tainted, instead you have to talk about a pair of addresses
being tainted with each other. So even though it's hard to reason about
the exact algorithm we can still talk about likely situations, and
imagine what an adversary could do in the worst case or best case.

One way to resist a likely taint analysis attack is to involve other
parts of the bitcoin economy in your transactions. For example our
exchange thief could deposit and then withdraw his stolen coins through
a Bitcoin Casino or other bitcoin service hot wallet. His coins might no
longer be 100% tainted from the exchange hack but perhaps have 5%
exchange hack, 5% bitcoin ATM, 5% mined coins, etc etc. The numbers are
made up and they depend on the exact algorithm but the main point is
that involving the rest of the bitcoin economy in your transaction is
one practical way to stop taint analysis being a useful attack against
on you.

Another important point is that taint isn't part of bitcoin's code
anywhere. It is an external reality that surveillance companies impose
on users. The only reason taint has any influence is because of
censorship, for example an exchange 

Re: [bitcoin-dev] Question about PayJoin effectiveness

2020-06-10 Thread Chris Belcher via bitcoin-dev
On 10/06/2020 05:01, Mr. Lee Chiffre via bitcoin-dev wrote:
> I am trying to learn about payjoin. I have a couple concerns on its
> effectiveness. Are my concerns valid or am I missing something?
> 
> concern 1
> If it is known to be a payjoin transaction anyone could determine the
> sender the recipient and amount right?
> 
> Lets assume that everyone has a single utxo because payjoin becomes common
> use and payjoin consolidates utxos through "snowballing". If Alice has a
> UTXO of 0.05 btc and Bob has a UTXO of 1.15 btc. Bob can be assumed to
> have more balance because he is a merchant and his customers payjoin him
> payments alot.
> 
> If Alice and Bob do a payjoin with Alice paying 0.01 btc to Bob, it would
> probably look like this right?
> 
>  0.05---> |>1.16
>  1.15---> |>0.04
> 
> It is very obvious here the amount sent and the sender.  Even if Alice did
> combine another input it would still be very obvious. In this case Alice
> has another utxo with 0.4 BTC
> 
>  0.40---> |
>  0.05---> |>1.16
>  1.15---> |>0.44
> 
> This is still obvious that Alice paid Bob 0.01 BTC isn't it?
> 
> 
> 
> concern 2
> If there is just one consolidated utxo after each payjoin, would it  be
> easy to break the privacy of transaction chains?
> 
> Alice---payjoin--->Bob
> Clark---payjoin--->Bob
> 
> or
> 
> Alice---payjoin--->Bob---payjoin--->Clark
> 
> For exmaple, lets say that Alice payjoins to Bob. Then later on Clark
> payjoins with Bob. Based on the payjoin between Clark and Bob, Clark now
> knows what UTXO was actually Bob's. And can then know which one was
> actually Alices. By transacting a payjoin with someone, they could decloak
> the payjoins before them right? If so, how far back the chain can they go?
> 
> The issue is not that someone knows the utxos of themselves and the entity
> they payjoined with. The issue is that someone can figure out the payjoins
> of others before them with the same entity.
> 
> 
> I surely must be missing something here. What am I not understanding?
> 

Adding to what other people have written, it's an important point that
PayJoin breaks the common-input-ownership heuristic. I.E. if PayJoins
become even moderately popular then it will no longer be a safe
assumption that all the inputs to a transaction are owned by the same
entity (taking away all the obvious breaks like equal-output-coinjoins).

This assumption is a huge reason why blockchain surveillance is so
effective. A good paper on that is here:
https://arxiv.org/abs/1605.06369 (The Unreasonable Effectiveness of
Address Clustering Harrigan, Martin & Fretter, Christoph. (2016))

The assumption is mentioned by Satoshi in the whitepaper where he
laments that the privacy loss is unavoidable. (One of the few outright
errors in the paper, perhaps the only error). The fact that we have
technology to break this assumption is a massive deal, and that's a big
value-add of PayJoin.

___
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-06-10 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

On 10/06/2020 11:58, ZmnSCPxj wrote:
> Good morning Chris,
> 
>>> Let me propose an alternative: swap-on-receive+swap-on-change.
>>
>> That's an interesting point, thanks for the thought. This scheme might
>> not be appropriate for every threat model and use case.
>> For example, if someone wants to use bitcoin just as a foreign currency
>> for its privacy and censorship-resistant properties. So for example if
>> they want to pay for a VPN anonymously, so they buy bitcoins and
>> immediately send all of them to the VPN merchant. The swap-on-receive
>> wouldn't be appropriate for them because they'll be doing a coinswap
>> straight away to the VPN merchant. So perhaps this plan could be an
>> optional mode of operation (which may or may not be the default). The
>> scheme obviously is useful when bitcoin is being used more as a
>> day-to-day money.
> 
> 
> No, I think you misunderstand my proposal.
> 
> If the user is doing swap-on-receive, the user already has an anonymous UTXO, 
> they can just transfer it directly in full to the VPN without using a 
> CoinSwap.
> 
> The number of CoinSwaps involved is the same: one.
> 
> So the difference is:
> 
> * swap-on-receive:
>   * I get some coins from an exchange, giving them my contact information and 
> bank information and all the places I have ever inhabited in my entire 
> existence and an unfertilized egg sample and an archive of my diary and let 
> them invasively scan my cognitive substrate.
>   * I send the coins to my CoinSwap wallet.
>   * The CoinSwap wallet automaticaly CoinSwaps the coins into a new UTXO.
> * One CoinSwap.
>   * I tell the CoinSwap wallet to send it all to the VPN.
> * My CoinSwap wallet knows my coins are already cleaned, so it creates a 
> plain 1-input 1-output transaction directly to the VPN address.
> 
> * swap-on-pay:
>   * I get some coins from an exchange, giving them my contact information and 
> bank information and all the places I have ever inhabited in my entire 
> existence and an unfertilized egg sample and an archive of my diary and let 
> them invasively scan my cognitive substrate.
>   * I send the coins to my CoinSwap wallet.
>   * I tell the CoinSwap wallet to send it all to the VPN.
> * My CoinSwap wallet automatically arranges a CoinSwap into the VPN 
> address.
>   * One CoinSwap.
> 
> So in both cases the same expected number of CoinSwaps is done, i.e. one.
> 
> Note that there are still details like how much onchain fees are and how much 
> CoinSwap maker fees are and etc etc but they exist for both flows anyway.
> So I would still be buying slightly more than my target amount, and if there 
> is any change I could just designate it to be added to the mining fees or a 
> donation to ZmnSCPxj, because ZmnSCPxj is so awesome.
> 
> What swap-on-receive+swap-on-change instead does is just amortize the timing 
> of the CoinSwaps, so that you CoinSwap as soon as you receive, instead of as 
> soon as you have to pay, so that sending payments is as fast as non-CoinSwap 
> onchain wallets.
> 
> 
> Regards,
> ZmnSCPxj
> 

Right, I get it. Good explanation.

In your swap-on-receive example the exchange also can't tell how long
your coins remain unspent in your wallet, which they could in
swap-on-pay. This is very useful information for an exchange because it
tells them about what hodlers are doing, and they might trade against
them. (e.g. opening big short positions right after they see many long
term hodl'd coins being moved)

___
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-06-10 Thread Chris Belcher via bitcoin-dev
Hello Lee,

Thanks for the review.

On 10/06/2020 01:43, Mr. Lee Chiffre wrote:
> 
>>
>> === Combining multi-transaction with routing ===
>>
>> Routing and multi-transaction must be combined to get both benefits. If
>> Alice owns multiple UTXOs (of value 6 BTC, 8 BTC and 1 BTC) then this is
>> easy with this configuration:
>>
>>  Alice
>> (6 BTC) (8 BTC) (1 BTC)
>>|   |   |
>>|   |   |
>>v   v   v
>>   Bob
>> (5 BTC) (5 BTC) (5 BTC)
>>|   |   |
>>|   |   |
>>v   v   v
>> Charlie
>> (9 BTC) (5 BTC) (1 BTC)
>>|   |   |
>>|   |   |
>>v   v   v
>> Dennis
>> (7 BTC) (4 BTC) (4 BTC)
>>|   |   |
>>|   |   |
>>v   v   v
>>  Alice
>>
> 
> 
> 
> 
> 
> 
> Great work Chris and you have my respects for your contributions to
> Bitcoin. A concern I have with bitcoin is scalability and privacy. Both
> are important. The reasons people bash on Monero is also the same issue
> Bitcoin has. The very large transaction size to achieve acceptable privacy
> on a distributed financial network. Im not shilling Monero here. I am only
> saying that bitcoin transactions with similar privacy properties are at
> least equally as large as Monero transactions. Coinjoin on Monero can be
> compared to ring signatures in Monero from the view of using decoys to
> help conceal the source. From this proposal is this to say that
> transactions will be at least 12 times larger in size to achieve the
> property of privacy that bitcoin is currently missing?
> 
> Another thing to consider is that if coinswaps cannot be sent as a payment
> then a coinswap needs to take place after every transaction to keep the
> privacy and unlinkability from your other bitcoin transactions.
> 
> I always thought that CoinSwap would be and is a very much needed thing
> that needs developed. The ability to swap coins with other people in a
> trustless way and way that is not linkable to the public blockchain. But
> how can this be scalable at all with the multiple branches and layers?
> This is a good idea in theory but my concern would be the scalability
> issues this creates.
> 
> Do you have any comments on this?
> Thank you
> 

You are right to be concerned about scalability.

Here's a few of my thoughts on this:

An issue with Monero (or any cryptocurrency based on the ring signature
input signing scheme) isn't just that transactions are bigger in bytes.
Monero full nodes can't know when a TXO has been spent, so pruning is
impossible in Monero and the list of TXOs perpetually grows, this is
unlike in bitcoin where full nodes know if a UTXO has been spent and so
can delete it in pruning. The storage space needed for Bitcoin's UTXO
set sometimes actually gets smaller.

Note that Monero software actually has a feature called "pruning" so
sometimes the terminology gets confused when people say "wait, Monero
_does_ have pruning". But this pruning doesn't do the same thing as
Bitcoin's pruning, the disk space still grows as O(TXOcount) which is
much faster compared to Bitcoin's O(UTXOcount).

And when designing this CoinSwap system I've been careful to make sure
it doesn't break pruning (or other resources saving features, for
example CoinSwap can be made to work with the blocksonly feature of
Bitcoin Core). So bitcoin-with-CoinSwap's scalability isnt anywhere near
as bad as Monero's.

You're right to talk about decoys. Decoys are not a good way to obtain
privacy because they can be broken by repeated interactions.. I really
like this talk about why decoys are not a good solution to privacy in
many cases:

talk: https://www.youtube.com/watch?v=YgtF7psIKWg=youtu.be=3701
transcript:
https://tokyo2018.scalingbitcoin.org/transcript/tokyo2018/how-much-privacy-is-enough

Equal-output CoinJoins also work with decoys. Like in JoinMarket you
could analyze those CoinJoins to say that the inputs and outputs of the
makers in a CoinJoin are actually just decoys. Fixed-denomination
CoinJoins like in Wasabi or Samourai also use much more block space
because of the reduced divisibility, for example Wasabi coinjoins can
only be done with about 0.1 BTC, so if you want to mix 1 BTC then you
have to do 10 such CoinJoins, costing 10 times the block space.

CoinSwap doesn't work by adding decoys, it improves privacy in the same
way as Lightning: by moving information off-chain.

You could perhaps analyze CoinSwap as using decoys if you say that the
decoys are almost every other bitcoin transaction happening on the
blockchain, and that can be almost as big as you want. One full block
has about 3000 outputs, so if you wait a day between the CoinSwap
funding and spending transactions then that's 144*3000 = 432000 decoys
(this calculation is simplified, but it's a good starting point). If
CoinJoin or Monero transactions had that 

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

2020-06-10 Thread Chris Belcher via bitcoin-dev
Good morning ZmnSCPxj,

On 06/06/2020 02:40, ZmnSCPxj wrote:
> Good morning Chris,
> 
>> I think I'm having trouble understanding this, does it work like this:
>>
>> Say we're in the 2-party coinswap case (Alice and Bob)
>>
>> We have Alice's funding transaction:
>> Alice UTXO ---> 2of2 multisig (Alice+Bob)
>>
>> And we have the regular contract transaction
>> 2of2 multisig (Alice+Bob) ---> Alice+timelock1 OR Bob+hashlock
>>
>> And you propose a second pre-signed transaction?
>> 2of2 multisig (Alice+Bob) ---> Bob+timelock2
> 
> No, it is:
> 
> 2of2 multisig (Alice+Bob) --(nLockTime=locktime1)-> Alice
> 
> The timelock is  imposed as a `nLockTime`, not as an `OP_CLTV` (so not in the 
> output of the tx, but part of the tx), and the backout returns the funds to 
> Alice, not sends it to Bob.
> This transaction is created *before* the contract transaction.
> 
> The order is:
> 
> * Create (but not sign) Alice funding tx (Alice --> Alice+Bob).
> * Create and sign Alice backout transaction (Alice+Bob 
> -(nLockTime=locktime1)-> Alice).
> * Create (but not sign) Bob funding tx (Bob --> Alice+Bob+sharedSecret).
> * Create and sign Bob backout transaction (Alice+Bob+sharedSecret 
> -(nLocktime=locktime2)-> Bob) where timelock2 < timelock1.
> * Sign and broadcast funding txes.
>   * At this point, even if Bob funding tx is confirmed but Alice funding tx 
> is not, Bob can recover funds with the backout, but Alice cannot steal the 
> funds (since there is no hashlock branch at this point).
> * When Alice funding tx is confirmed, create and sign contract transaction 
> (Alice+Bob --> Alice+timelock1 OR Bob+hashlock).
> * When Bob funding tx is confirmed and Bob has received the Alice contract 
> transaction, create and sign Bob contract transaction (Alice+Bob+sharedSecret 
> --> Bob+timelock2 OR Alice+hashlock).
> * Continue as normal.
> 
> In effect, the backout transaction creates a temporary Spilman unidirectional 
> time-bound channel.
> We just reuse the same timelock on the HTLC we expect to instantiate, as the 
> time bound of the Spilman channel; the timelock exists anyway, we might as 
> well reuse it for the Spilman.
> 
> Creation of the contract tx invalidates the backout tx (the backout tx is 
> `nLockTime`d, the contract tx has no such encumbrance), but the backout 
> allows Alice and Bob to fund their txes simultaneously without risk of race 
> loss.
> However, they do still have to wait for (deep) confirmation before signing 
> contract transactions, and Bob has to wait for the incoming contract 
> transaction as well before it signs its outgoing contract transaction.
> 
> The protocol is trivially extendable with more than one Bob.
> 
> The insight basically is that we can split CoinSwap into a "channel 
> establishment" phase and "HTLC forwarding" phase followed by "HTLC 
> resolution" and "private key handover".
> HTLC forwarding and HTLC resolution are "done offchain" in the channels, and 
> channel establishment can be done in any order, including reverse.
> 
> Indeed, the Spilman channel need not have the same timelock as the HTLC it 
> will eventually host: it could have a shorter timelock, since the contract 
> transaction has no `nLockTime` it can be instantiated (with loss of privacy 
> due to the nonstandard script) before the Spilman timeout.
> 
> Regards,
> ZmnSCPxj
> 

Thanks for the explanation. I understand now, and I understand how this
makes it possible for all funding transactions in a coinswap route to be
confirmed in the same block.

However, I think this also breaks private key handover. Here's why:

Recall that in a Alice/Bob coinswap we have two funding transactions
(Alice --> multisig(Alice, Bob) and Bob --> multisig(Bob,Alice)), and
two contract transactions (multisig(Alice, Bob) -->
Alice+OP_CSV_timelock OR Bob+hashlock and multisig(Bob,Alice -->
Bob+OP_CSV_timelock OR Alice+hashlock). After the hashlock preimage
becomes known to all then Alice and Bob give their multisig privkey to
the other party.

Bob now has both privkeys in the multisig(Alice,Bob) so he can sign any
transaction he wants spending from it, but the contract transaction
still exists. So until Bob actually spends from the multisig he must
always be watching the blockchain, and if Alice broadcasts the contract
transaction then Bob must immediately spend from it using the hash
preimage branch. If Bob waits too long and the OP_CSV timelock value
passes then Alice can steal Bob's money by spending with that path. The
OP_CSV timelock only starts ticking when the contract transaction
actually confirms, and this is crucial for making privkey handover
practical because it means the coins in the multisig can stay unspent
indefinitely.

However, I think this does not apply to the scheme you described which
uses nLockTime, because after the privkeys are handed over Alice's
backout transaction (Alice+Bob -(nLockTime=locktime1)-> Alice) still
exists, and Alice could broadcast it. Once locktime1 passes then Alice
can 

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

2020-06-05 Thread Chris Belcher via bitcoin-dev
Good day ZmnSCPxj,

>>> 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.
>>
>> I think this is wrong, and that it's possible for the funding
>> transactions of chained/routed swaps to all be in the same block as well.
>>
>> In CoinSwap it's possible to get DOS'd without the other side spending
>> money if you broadcast your funding transaction first and the other side
>> simply disappears. You'd get your money back but you have to waste time
>> and spend miner fees. The other side didn't spend money to do this, not
>> even miner fees.
>>
>> From the point of view of us as a maker in the route, we know we won't
>> get DOS'd like this for free if we only broadcast our funding
>> transaction once we've seen the other side's funding transaction being
>> broadcast first. This should work as long as the two transactions have a
>> similar fee rate. There might be an attack involving hash power: If the
>> other side has a small amount of hash power and mines only their funding
>> transaction in a manner similar to a finney attack, then our funding
>> transaction should get mined very soon afterwards by another miner and
>> the protocol will continue as normal. If the other side has knowledge of
>> the preimage and uses it to do CPFP and take the money, then we can
>> learn that preimage and do our own CPFP to get our money back too.
> 
> How about RBF?
> 
> A taker Alice can broadcast the funding tx spending its own funds.
> The funding tx spends funds controlled unilaterally by Alice.
> Alice can sign a replacement transaction for those funds, spending them to an 
> address with unilateral control, and making the funding tx output with all 
> the obligations attached never get confirmed in the first place.
> 
> The chances may be small --- Bob can certainly monitor for Alice broadcasting 
> a replacement and counter-broadcast its own replacement --- but the risk 
> still exists.
> TANSTAAGM (There Aint No Such Thing As A Global Mempool) also means Alice 
> could arrange the replacement by other means, such as not using the 
> RBF-enabled flag, broadcasting the self-paying replacement near miner nodes, 
> and broadcasting the CoinSwap-expected funding tx near the Bob fullnode; Bob 
> fullnode will then reject attempts to replace it, but miners will also reject 
> the CoinSwap-expected funding tx and it will not confirm anyway.
> 
> 
> With the pre-SAS 4-tx setup, this potentially allows Alice to steal the funds 
> of Bob; after Alice gets its funding-tx-replacement confirmed together with 
> the Bob honest-funding-tx, Alice can use the contract transaction and publish 
> the preimage to take the Bob funds.
> Since the Alice-side funding tx has been replaced, knowledge of the hash 
> preimage will not help Bob any: the Alice funding tx has been replaced and 
> Bob cannot use the preimage to claim it (it does not exist).
> 
> 
> With SAS Alice cannot outright steal the Bob funds, but the Bob funds will 
> now be locked in a 2-of-2 and Alice can take it hostage (either Bob gives up 
> on the funds, i.e. donates its value to all HODLers, or Bob gives most of the 
> value to Alice).
> 
> 
> For the avoidance of theft, it is probably better for Bob to wait for 
> Alice-side funding tx to confirm, probably deeply because reorgs suck.
> 
> This at least makes it costly to perform this attack; you have to lock more 
> of your funds longer in order to induce a competitor to lock its funds.
> 
> 
> Come to think of it, the same issue probably holds for S6 as well, the 
> funding tx with the longest timelock has to confirm first before the next is 
> even broadcast, bleah.

Your RBF observation actually blows my idea out of the water. Not just
because of RBF but because of an attack by a miner.

Supposing that Alice starts with knowledge of the hash preimage, if she
uses RBF to make her funding transaction never confirm but allows Bob's
funding transaction to confirm, then Alice can use her preimage to take
the money from Bob's funding transaction. Bob will learn the value of
the preimage but it won't be much good to him because Alice's funding
transaction isn't valid anymore. Alice will get money from her funding
transaction and also money from Bob's funding transaction.

Because of this attack, it's pretty clear that a CoinSwap peer who
starts _without_ knowledge of the preimage must wait for the other
side's funding transaction to actually confirm, perhaps even with
multiple confirmations if they fear that the other side has access to
hashpower. For example, a miner could play the role of Alice and use
this attack to almost-risklessly steal Bob's 

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

2020-06-02 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

On 31/05/2020 03:30, ZmnSCPxj via bitcoin-dev wrote:
> Good morning Ruben and Chris,

> 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 main benefit of PayJoin-with-CoinSwap is it breaks the
common-input-ownership heuristic, which is a major widely used
heuristic. It would be a big win if that heuristic could be broken.

PayJoin-with-CoinSwap would be useful if Alice is trying to recover some
privacy which was previously degraded, for example if she is spending
from a reused address or from an address linked to her identity. If she
does a PayJoin with the reused address then some other economic entity
would have his activity linked with Alice's.

Just the fact that PayJoin-with-CoinSwap exists would improve privacy
for people who don't use it, for example if someone buys bitcoin from an
exchange that knows their identity and then co-spends it with other
coins they obtained another way. The fact that PayJoin exists means an
adversary cannot assume for sure that this user really owns that other
address which was co-spent. This doesn't apply for regular CoinSwap,
which only ever breaks the transaction graph heuristic, so in our
example the destination the coins are sent *to* would be uncertain, but
that the co-spent inputs are owned by the same person would be certain
in a world where PayJoin didn't exist.

> 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.

Opening up the possibility of spying for free is a real downside for
PayJoin-with-CoinSwap. Using decoy UTXOs as described in my design
document, rather than PoDLE, seems like a better way of resisting these
attacks. This is because at the cost of a little bit more bandwidth and
CPU its possible to make the probability of an attacker successfully
guessing the maker's real UTXOs to be as low as you want.

> 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.

I think this is wrong, and that it's possible for the funding
transactions of chained/routed swaps to all be in the same block as well.

In CoinSwap it's possible to get DOS'd without the other side spending
money if you broadcast your funding transaction first and the other side
simply disappears. You'd get your money back but you have to waste time
and spend miner fees. The other side didn't spend money to do this, not
even miner fees.

>From the point of view of us as a maker in the route, we know we won't
get DOS'd like this for free if we only broadcast our funding
transaction once we've seen the other side's funding transaction being
broadcast first. This should work as long as the two transactions have a
similar fee rate. There might be an attack involving hash power: If the
other side has a small amount of hash power and mines only their funding
transaction in a manner similar to a finney attack, then our funding
transaction should get mined very soon afterwards by another miner and
the protocol will continue as normal. If the other side has knowledge of
the preimage and uses it to do CPFP and take the money, then we can
learn that preimage and do our own CPFP to get our money back too.

So in a routed coinswap setup it should be possible for Alice the taker
to broadcast her funding transaction first, which will lead to all the
makers broadcasting their funding transactions as well once they see the
other side has broadcast first. Then it would be possible for all those
funding transactions to be confirmed in the same block.

I hope I haven't missed anything, because if this doesn't work and each
maker must wait for confirmations, then the UX of routed CoinSwap would
degrade: a CoinSwap route of 5 makers would require at least 5 blocks to
be mined.

Of course this setup can leak the ordering of the routes because the
funding transaction would appear in the mempool in that order, but this
could be beaten if some Alices choose to intentionally spread out the
funding transaction broadcasts among multiple blocks for privacy reasons.

An interesting tangent could be to see if it's possible to make private
key 

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

2020-05-25 Thread Chris Belcher via bitcoin-dev
=== 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 transactions with much greater privacy.

== CoinSwap ==

Like CoinJoin, CoinSwap was invented in 2013 by Greg Maxwell[1]. Unlike
CoinJoin it is relatively complicated to implement and so far has not
been deployed. But the idea holds great promise, and fixes many of the
problems of some kinds of CoinJoins. CoinSwap is the next step for
on-chain bitcoin privacy.

CoinSwap is a way of trading one coin for another coin in a
non-custodial way. It is closely related to the idea of an atomic swap.
Alice and Bob can trade coins with each other by first sending to a
CoinSwap address and having those coins then sent to Bob:

Alice's Address 1 > CoinSwap Address 1 > Bob's Address 1

An entirely separate set of transactions gives Bob's coins to Alice in
return:

Bob's Address 2 > CoinSwap Address 2 > Alice's Address 2

Where the symbol > is a bitcoin transaction.

Privacy is improved because an observer of the blockchain cannot link
Alice's Address 1 to Alice's Address 2, as there is no transaction
between them. Alice's Address 2 could either be an address in Alice's
wallet, or the address of someone else she wants to transfer money to.
CoinSwap therefore breaks the transaction graph heuristic, which is the
assumption that if a transaction A -> B is seen then the ownership of
funds actually went from A to B.

CoinSwap doesnt break any of bitcoin's assumptions or features like an
auditable supply or pruning. It can be built on today's bitcoin without
any new soft forks.

CoinSwap can't improve privacy much on its own, so it requires other
building block to create a truly private system.

=== ECDSA-2P ===

The original CoinSwap idea uses 2-of-2 multisig. We can get a slightly
bigger anonymity set by using 2-of-3 multisigs with a fake third public
key. 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[2]. Even the old-style p2pkh addresses
starting with 1 can be CoinSwap addresses.

Because the transactions blend in with the rest of bitcoin, an
application based on CoinSwap would provide much more privacy than the
existing equal-output coinjoin apps (JoinMarket, Wasabi Wallet and
Samourai Wallet's Whirlpool). CoinSwaps would also be cheaper for the
same amount of privacy, as CoinJoin users usually create multiple
CoinJoins to get effective privacy, for example JoinMarket's tumbler
script does between 7-12 coinjoins (which are bigger than regular
transactions too) when run with default parameters.

Schnorr signatures with Musig provide a much easier way to create
invisible 2-of-2 multisig, but it is not as suitable for CoinSwap. This
is because the anonymity set for ECDSA would be much greater. All
addresses today are ECDSA, and none are schnorr. We'd have to wait for
schnorr to be added to bitcoin and then wait for users to adopt it. We
see with segwit that even after nearly 3 years that segwit adoption is
only about 60%, and segwit actually has a sizeable financial incentive
for adoption via lower fees. Schnorr when used for single-sig doesn't
have such an incentive, as Schnorr single-sig costs the same size as
today's p2wpkh, so we can expect adoption to be even slower. (Of course
there is an incentive for multisig transactions, but most transactions
are single-sig). As schnorr adoption increases this CoinSwap system
could start to use it, but for a long time I suspect it will mostly be
using 

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

2020-05-12 Thread Chris Belcher via bitcoin-dev
Hello list,

This proposal is very cool. It is very useful to have a coinswap scheme
requiring only two transactions.

As well as improving the scalability of the system by saving block
space, it also improves privacy because the coins could stay unspend for
a long time, potentially indefinitely. While in the original coinswap
proposal an analyst of the chain would always see a funding transaction
followed closely in time by a success transaction, and this could be
used as a fingerprint.

On 11/05/2020 18:50, Ruben Somsen via bitcoin-dev wrote:
> 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, 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
> 
> 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

You could create an old-style coinswap scheme using relative timelocks
(with OP_CSV). The original proposal uses absolute timelocks but there's
no reason relative timelocks can't be used instead, as long as the party
who starts with knowledge of the preimage has a timelock further away in
the future.

Using relative timelocks and private key handover for old-style
coinswaps would give us the same two-transaction effect and the
corresponding efficiency and privacy gains.

Of course we still don't get the effect that the swap on the other side
never expires.

A fun fact is that the idea of private key handover was mentioned as
early as 2016 in the original Lightning Network paper. The bottom of
page 27 says: "Instead  of disclosing the BR1a/BR1b signatures, it’s
also possible to just disclose the private keys to the counterparty.
This is more effective as described later in the key storage section".
Although it looks like nobody thought to apply it to coinswap or
realized the benefits.


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


Re: [bitcoin-dev] On the scalability issues of onboarding millions of LN mobile clients

2020-05-12 Thread Chris Belcher via bitcoin-dev
On 05/05/2020 16:16, Lloyd Fournier via bitcoin-dev wrote:
> On Tue, May 5, 2020 at 9:01 PM Luke Dashjr via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
>> On Tuesday 05 May 2020 10:17:37 Antoine Riard via bitcoin-dev wrote:
>>> Trust-minimization of Bitcoin security model has always relied first and
>>> above on running a full-node. This current paradigm may be shifted by LN
>>> where fast, affordable, confidential, censorship-resistant payment
>> services
>>> may attract a lot of adoption without users running a full-node.
>>
>> No, it cannot be shifted. This would compromise Bitcoin itself, which for
>> security depends on the assumption that a supermajority of the economy is
>> verifying their incoming transactions using their own full node.
>>
> 
> Hi Luke,
> 
> I have heard this claim made several times but have never understood the
> argument behind it. The question I always have is: If I get scammed by not
> verifying my incoming transactions properly how can this affect anyone
> else? It's very unintuative.  I've been scammed several times in my life in
> fiat currency transactions but as far as I could tell it never negatively
> affected the currency overall!
> 
> The links you point and from what I've seen you say before refer to "miner
> control" as the culprit. My only thought is that this is because a light
> client could follow a dishonest majority of hash power chain. But this just
> brings me back to the question. If, instead of BTC, I get a payment in some
> miner scamcoin on their dishonest fork (but I think it's BTC because I'm
> running a light client) that still seems to only to damage me. Where does
> the side effect onto others on the network come from?
> 
> Cheers,
> 
> LL
> 

Hello Lloyd,

The problem comes when a large part of the ecosystem gets scammed at
once, which is how such an attack would happen in practice.

For example, consider if bitcoin had 1 users. 10 of them use a full
node wallet while the other 9990 use an SPV wallet. If a miner attacked
the system by printing infinite bitcoins and spending coins without a
valid signature, then the 9990 SPV wallets would accept those fake coins
as payment, and trade the coins amongst themselves. After a time those
coins would likely be the ancestors of most active coins in the
9990-SPV-wallet ecosystem. Bitcoin would split into two currencies:
full-node-coin and SPV-coin.

Now the fraud miners may become well known, perhaps being published on
bitcoin news portals, but the 9990-SPV-wallet ecosystem has a strong
incentive to be against any rollback. Their recent transactions would
disappear and they'd lose money. They would argue that they've already
been using the coin for a while, and it works perfectly fine, and anyway
a coin that can be spent in 9990 places is more useful than one that can
be spent in just 10 places. The SPV-wallet community might even decide
to use something like `invalidateblock` to make sure their SPV-coin
doesn't get reorg'd out of existence. There'd also likely be a social
attack, with every bitcoin community portal being flooded with bots and
shills advocating the merits of SPV-coin. This is not a hypothetical
because we already saw the same thing during the scalability conflict
2015-2017.

Before you know it, "Bitcoin" would become SPV-coin with inflation and
arbitrary seizure. Any normal user could download software called
"Bitcoin wallet" which they trust and have used before, but instead of
using Bitcoin they'd be using SPV-coin. You may be one of the 10 wallets
backed by a full node, but that won't do much good to you when 9990
users happily use another coin as their medium of exchange.

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


Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

2020-05-03 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

>>> This "as long as the inputs that should be separate are not co-spent" is 
>>> precisely what mixdepths protect against, which is why I think some kind of 
>>> mixdepth facility will still matter in CoinSwap.
>>> Still, you have convinced me that, for the purpose of multi-transaction 
>>> CoinSwap where you do not merge any of your coins, it is immaterial if the 
>>> sub-transactions come from the same mixdepth or not.
>>> And if you have to merge your coins (for instance, if you are a maker and 
>>> your customer wants to get a UTXO that is larger than any you have on hand, 
>>> you have to merge your coins), you just have to ensure they are in the same 
>>> mixdepth.
>>> Of course, you could be proposing some other construct --- perhaps you have 
>>> some relational entry which says "you cannot merge coin A and coin B" which 
>>> allows you to merge A C D or B C E, but not A B?
>>> (I imagine this would make coin selection even harder, but I am not a 
>>> mathematician and there may be some trivial solution to this.)
>>> Now --- if you have two coins that cannot be merged in the same onchain tx, 
>>> what happens when you swap them in a multi-tx CoinSwap with somebody else?
>>> That somebody else does not know that information.
>>> Instead, that somebody else must always assume that any coins it got from 
>>> the same CoinSwap operation must not be safely mergeable (though they can 
>>> still be used in the same swap together).
>>> Coins received via receive addresses would also not be mergeable with any 
>>> other coins, except coins to the same address (because coins in the same 
>>> address already leak that they are owned by the same owner).
>>
>> Yes I guess you're right. This part about mixdepths requires further
>> thought.
>>
>> CoinSwap can be combined with some kind of CoinJoin (most likely
>> something similar to PayJoin or CoinJoinXT). That should help with the
>> reasoning about co-spending inputs and mixdepths, because other inputs
>> that are not owned by the taker will often be co-spent anyway.
>>
>> Regarding coins which mustn't be co-spent being coinswapped to somebody
>> else, ideally that coinswap maker will receive coins from unrelated
>> takers too, so will merge their coins along with those as well. Also the
>> fact that a coinswap happened means there are two transactions between
>> the taker's-inputs-which-mustnt-be-merged and them actually being merged.
> 
> One of those transactions (the second one) will be a 1-input 1-output tx (it 
> moves the coin from bilateral control to unilateral control of Bob), which 
> chain analysis already knows to be a self-transfer.
> The first transaction will also usually be a 1-input 1-output tx as well (it 
> moves the coin from unilateral of Alice to bilateral control) if you did not 
> do any splitting or merging before providing the coin into the swap (for 
> example if this comes from the taker, and the taker knows all the coins it 
> wants to swap cannot be safely merged together).
> 
> If chain analysis keeps the heuristic "1-input 1-output is a self-payment 
> because srsly who has an exact amount for a payment Bitcoin is volatile lol", 
> then the resulting coins still are not safe to merge, because chain analysis 
> will "pass through" the swap operation and if the two coins are later merged 
> then they still end up *correctly* concluding the original coins were owned 
> by the same owner.
> 
> Using a PayJoin construction for the second tx would help, but if the 
> receiving end does not have a spare UTXO it can merge with (e.g. all its 
> liquidity got tied up in the swap) then there might not be an opportunity to 
> PayJoin.
> 
> There is also little that can be done about the first transaction, in case it 
> ends up being a 1-input 1-output.
> 
> Suppose Alice the taker has a 1 BTC output and a 1 BTC output *and no other 
> coins*, both of which it cannot safely merge, and it has to pay 1.2 BTC to 
> Carol.
> Alice then has to CoinSwap them to Bob the maker, requesting a 1.2 BTC output 
> going to Carol and the rest in whatever loose change Bob has.
> Alice then has to use two 1-input 1-output txes for each of its 1 BTC outputs 
> (because it cannot merge them together) to put them into bilateral control.
> Then Bob claims them from bilateral control with 1-input 1-output txes as 
> well (it cannot merge them together, because that might break Alice privacy, 
> and Bob might not have any other spare coins it can merge with the incoming 
> funds).
> 
> Now, even if Bob PayJoins the second tx for both 1 BTC outputs, it still 
> cannot merge the resulting joined coins together, because the 
> "spent-together" analysis would still tie those coins as being owned by the 
> same owner, it is simply that the surveillor will think the owner owns more 
> coins than it actually does, but the two 1 BTC TXOs that Alice used to own 
> are still analyzed as being owned by the same owner if they are ever merged.
> 
> What 

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

2020-04-30 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,

On 30/04/2020 09:54, ZmnSCPxj wrote:
> Good morning CB,
> 
> 
>> Equal-output-coinjoins and JoinMarket also have a version of the
>> common-input-ownership-heuristic (CIOH), because its often possible to
>> separate the inputs into sets of their owners of a equal-output-coinjoin
>> using the input amounts. CoinSwap can be combined with something like
>> PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
>> system wouldn't have this flaw either.
>>
>> For those reasons I've been thinking a CoinSwap system wouldn't need as
>> many mixdepths, maybe it could use two or even just one.
> 
> Would the ZeroLink proposal of separating a receiving (pre-mix) wallet from a 
> sending (post-mix) wallet apply, thus having two implicit mixdepths (the 
> receiving mixdepth and the sending mixdepth)?
> Or would imposing the rule "all sends must be via CoinSwap" be sufficient 
> (and follow the ZeroLink rule in spirit)?
> 
>> If so, then it follows that multi-transaction CoinSwaps can be done by
>> having UTXOs come from the same mixdepth, as long as the inputs that
>> should be separate are not co-spent in the same transaction.
> 
> This "as long as the inputs that should be separate are not co-spent" is 
> precisely what mixdepths protect against, which is why I think *some* kind of 
> mixdepth facility will still matter in CoinSwap.
> 
> Still, you have convinced me that, for the purpose of multi-transaction 
> CoinSwap where you do not merge any of your coins, it is immaterial if the 
> sub-transactions come from the same mixdepth or not.
> And if you have to merge your coins (for instance, if you are a maker and 
> your customer wants to get a UTXO that is larger than any you have on hand, 
> you have to merge your coins), you just have to ensure they are in the same 
> mixdepth.
> 
> Of course, you *could* be proposing some other construct --- perhaps you have 
> some relational entry which says "you cannot merge coin A and coin B" which 
> allows you to merge A C D or B C E, but not A B?
> (I imagine this would make coin selection even harder, but I am not a 
> mathematician and there may be some trivial solution to this.)
> 
> Now --- if you have two coins that cannot be merged in the same onchain tx, 
> what happens when you swap them in a multi-tx CoinSwap with somebody else?
> That somebody else does not know that information.
> Instead, that somebody else must always assume that any coins it got from the 
> same CoinSwap operation must not be safely mergeable (though they can still 
> be used in the same swap together).
> 
> Coins received via receive addresses would also not be mergeable with any 
> other coins, except coins to the same address (because coins in the same 
> address already leak that they are owned by the same owner).

Yes I guess you're right. This part about mixdepths requires further
thought.

CoinSwap can be combined with some kind of CoinJoin (most likely
something similar to PayJoin or CoinJoinXT). That should help with the
reasoning about co-spending inputs and mixdepths, because other inputs
that are not owned by the taker will often be co-spent anyway.

Regarding coins which mustn't be co-spent being coinswapped to somebody
else, ideally that coinswap maker will receive coins from unrelated
takers too, so will merge their coins along with those as well. Also the
fact that a coinswap happened means there are two transactions between
the taker's-inputs-which-mustnt-be-merged and them actually being merged.

Great point on the receive addresses coins. Another use case of
mixdepths is to stop incoming payments from two different sources being
linked together.

>>> Assuming Alice is the taker, and Bob is the maker, then Alice might want a 
>>> specific coin value (or set of such) that Bob does not have.
>>> In that case, Bob will have to split a UTXO it owns.
>>> We could constrain it so that Bob at least is not allowed to use the change 
>>> from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC 
>>> coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split 
>>> its own 9 BTC coin then swap.
>>> Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing 
>>> UTXO in the same swap should be from different mixdepths.
>>
>> A good way to do it could be for Alice to tell Bob that she wants 10 BTC
>> and let Bob figure out on his own how to get that amount, based on the
>> amounts he already has. If Alice is making a payment she can provide
>> that amount too, but all the other output amounts can be up to Bob.
> 
> This leaks to Bob whether Alice is making a payment or not; it would be 
> better for the privacy of Alice for Alice to *always* mention *some* "payment 
> amount", even if this is not actually a payment and Alice is just mixing for 
> herself prior to storing in cold storage.
> And if Alice wants to use a single swap to pay to multiple targets at once, 
> that implies Alice has to have the 

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

2020-04-29 Thread Chris Belcher via bitcoin-dev
Hello ZmnSCPxj,


On 29/04/2020 08:56, ZmnSCPxj wrote:
> It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker 
> that also provides CoinSwap services using the same UTXOs.

A great benefit of a CoinSwap system is that the transactions are
steganographic. If equal-output-coinjoins were involved that benefit
would be lost. So it would be better if it didn't happen.

> However, this requires us to retain compatibility with the JoinMarket wallet 
> structure, which is divided into mixdepths, with the rule that UTXOs in 
> different mixdepths cannot be spent together in the same onchain UTXO (to 
> move across mixdepths you have to do a send, and sending out is always done 
> by a single CoinJoin round with multiple makers).
> I am uncertain what is the best way to handle multitransaction when 
> considering the mixdepth system.
> My instinct is that if you are doing multitransaction (whether as taker or 
> maker) then each transaction in the swap *has to* come from a different 
> mixdepth.
> The issue here is:
> 
> * If all the UTXOs in the multitransaction swap come from the same mixdepth, 
> then a surveillor who is monitoring that mixdepth gets a good hint in solving 
> the sparse subset sum problem.
> * On the other hand, if all the UTXOs in the multitransaction swap come from 
> different mixdepths, then a surveillor who has solved the sparse subset sum 
> problem now has the hint that the different mixdepths are really owned by the 
> same JoinMarket user.
> 
> I am uncertain which tradeoff is better here, though I am inclined to think 
> the latter is better.

JoinMarket has many mixdepths (5 by default) because it's
equal-output-coinjoins easily leak change addresses. CoinSwap
transactions don't have this flaw because they're steganographic. Such a
system could also be coded to intentionally break the weaker change
output heuristics
(https://en.bitcoin.it/wiki/Privacy#Change_address_detection).

Equal-output-coinjoins and JoinMarket also have a version of the
common-input-ownership-heuristic (CIOH), because its often possible to
separate the inputs into sets of their owners of a equal-output-coinjoin
using the input amounts. CoinSwap can be combined with something like
PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
system wouldn't have this flaw either.

For those reasons I've been thinking a CoinSwap system wouldn't need as
many mixdepths, maybe it could use two or even just one.

If so, then it follows that multi-transaction CoinSwaps can be done by
having UTXOs come from the same mixdepth, as long as the inputs that
should be separate are not co-spent in the same transaction.

Remember that a passive surveillor of the blockchain doesn't see
mixdepths at all, they see addresses and transactions, and must use
heuristics to try to cluster them together. We can break these heuristics.


> Attempting to completely detach a market-for-CoinSwap from JoinMarket seems 
> to be impossible to my mind: the protocols are known, implementations open, 
> and someone will inevitably write code for a single piece of software that 
> can operate as both a JoinMarket maker *and* a maker for a 
> market-for-CoinSwap (to increase their market, so to speak), so it might be 
> better to just add CoinSwap to JoinMarket in the first place.

Someone who has the ability to write such code should also have the
awareness to realize that mixing equal-output-coinjoins with coinswaps
damages the privacy because it breaks the steganography of coinswaps.

Also, because CoinSwap is better than equal-output CoinJoin in almost
every way, we can expect users (who are takers) to stop using JoinMarket
and switch over to CoinSwap if the software becomes mature. So such a
JoinMarket maker won't get many customers, and so there wouldn't be much
point writing such maker code.

But for sure it would be good to reuse code in any eventual
implementation. Indeed Waxwing's implementation did:
https://github.com/AdamISZ/CoinSwapCS

> Assuming Alice is the taker, and Bob is the maker, then Alice might want a 
> specific coin value (or set of such) that Bob does not have.
> In that case, Bob will have to split a UTXO it owns.
> 
> We could constrain it so that Bob at least is not allowed to use the change 
> from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC 
> coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split 
> its own 9 BTC coin then swap.
> Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing 
> UTXO in the same swap should be from different mixdepths.

A good way to do it could be for Alice to tell Bob that she wants 10 BTC
and let Bob figure out on his own how to get that amount, based on the
amounts he already has. If Alice is making a payment she can provide
that amount too, but all the other output amounts can be up to Bob.

Bob would often still have to split a UTXO he owns, but see below about
breaking change address 

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

2020-04-28 Thread Chris Belcher via bitcoin-dev
On 24/04/2020 02:34, ZmnSCPxj via bitcoin-dev wrote:
> Good morning Germán,
> 
> 
>> With regards to trying to tackle the problem of value-based correlations, 
>> wouldn't it be possible to try to model the solution after the 
>> equal-sum-subset problem (np complete problem)( 
>> https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf
>>   )? 
>> That is, a pair of individuals with a set of UTXOs that both add up to 
>> similar if not equal value perform a swap of similar-(total)value sets. In 
>> this way the values of the UTXOs can be broken up essentially at random 
>> (following some nominal distribution so that it doesn't stand out; e.g. 
>> https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction 
>> and decorrelated by using different keys + randomized locktimes.
> 
> There are a number of issues to simply modeling this to the subset-sum 
> problem.
> 
> * There is a practical limit to the number of UTXOs you would be willing to 
> receive in the swap.
>   * Every UTXO you receive increases the potential fee you have to pay to 
> spend them, meaning you would strongly dislike receiving 100 UTXOs that sum 
> up to 1mBTC.
>   * Thus, a practical blockchain analyst can bound the size of the sets 
> involved, and the problem becomes less than NP in practice.
> * If you have a single UTXO and split it, then swap, anyone looking at the 
> history can conjecture that the split involved is part of a CoinSwap.
>   * The split is now a hint on how the subset sums can be tried.
> * If after the CoinSwap you spend the UTXOs you received in a single 
> transaction, then you just published the solution to the subset sum for your 
> adversary.
>   * This ties in even further to the "practical limit on the number of UTXOs".
> * Because it is not safe to spend the UTXOs from a single CoinSwap 
> together, you want to have fewer, larger UTXOs for more flexibility in 
> spending later.
> 
> I believe belcher and waxwing and nopara73 have been working far longer on 
> privacy tech, and you should try to get in contact with them as well, they 
> may know of other issues (or solutions to the above problems).
> 
> Regards,
> ZmnSCPxj
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Hello list,

A couple of thoughts on multi-transaction coinswaps:

* Users should never split up a single UTXO before doing a coinswap,
instead they should send the one UTXO to a coinswap address and get back
multiple UTXOs.

For example, this 1-to-3 TXO coinswap (The symbol > means bitcoin
transaction).

AliceA (10 BTC) > CoinSwap AddressA > BobA (10 BTC)

BobB (3 BTC) > CoinSwap AddressB > AliceB (6 BTC)
BobC (2 BTC) > CoinSwap AddressC > AliceC (3 BTC)
BobD (5 BTC) > CoinSwap AddressD > AliceD (1 BTC)


Note that the Bob-to-Alice set of transactions add up to 10 BTC, the
entire CoinSwap is swapping the same amount.

Or written another way:

Alice TXO (10 BTC) > Coinswap Protocol > Alice TXO1 (6 BTC)
   > Alice TXO2 (3 BTC)
   > Alice TXO3 (1 BTC)

This kind of thing could also be used for consolidation of many UTXOs
without necessarily leaking information that the same person owns them.
For example, if Alice owns 5 UTXOs:

Alice TXO1 > Coinswap Protocol > Alice TXO
Alice TXO2 >
Alice TXO3 >
Alice TXO4 >
Alice TXO5 >


* It's helpful if any CoinSwap app is actually used for spending rather
than just mixing back to yourself. That will help avoid the problem of
users inadvertently co-spending all their coinswap outputs in the same
transaction.
An example of Alice paying for a VPN anonymously:

Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC)
  ---> Change1 (6 BTC)
  ---> Change2 (3 BTC)
  ---> Change3 (0.9 BTC)

In this case Alice will never accidentally merge all her TXOs together,
because the VPN Payment TXO doesn't belong to her. Also this could
improve privacy because unlike in normal transaction the VPN provider
might not be able to figure out the lower bound of Alice's balance (10
BTC in this case).


* Multi-transaction CoinSwaps aren't truly an example of a subset-sum
problem, but "sparse subset sum", a related and easier problem.

The way its normally formulated, subset sum is about finding a subset
that adds up to a target value. But in multi-transaction coinswap
there'd only be three or four CoinSwap outputs, so the problem is
finding just three or four integers in a big set that add up to the target.

You could think of it mathematically that the n-choose-k function is
near-polynomial when k 

[bitcoin-dev] Base64-encoded descriptors

2019-12-24 Thread Chris Belcher via bitcoin-dev
I've recently been playing around with descriptors, and they are very
nice to work with. They should become the standard for master public
keys IMO.

One downside is that users cant easily copypaste them to-and-fro to make
watch-only wallet. The descriptors contain parenthesis and commas which
stop highlighting by double-clicking. Also the syntax might look scary
to newbs.

An obvious solution is to base64 encode the descriptors. Then users
would get a text blog as the master public key without any extra details
to bother them, and developers can easily base64 decode for developing
with them.

A complication might be the descriptor checksum. If there's a typo in
the base64 text then that could decode into multiple character errors in
the descriptor, which might be problematic for the checksum. Maybe the
descriptor could be base64 encoded without the checksum, then attach the
checksum to the end of the base64 text.

Thoughts?

I didn't come up with these ideas, they came from discussions with achow101.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIPable-idea: Consistent and better definition of the term 'address'

2019-10-09 Thread Chris Belcher via bitcoin-dev
This is an excellent idea and I hope something like this happens.

I've had the idea of using an intermediate name to make the transition
easier, for example "Bitcoin address" becomes "Bitcoin invoice address"
which after 10 years becomes "Bitcoin invoice" (or "Bitcoin invoice").

"Invoice" would also work well because Lightning uses the name invoice
for the object which is used to receive payments. So it's easy to
imagine that the GUI text input presented to users can be called
"invoice" and users can put both kinds of invoices there leaving the
wallet to easily figure out whether it makes an on-chain transaction or
a Lightning Network transaction.

Changing a commonly-used name like this could be very hard, but the
gains in terms of privacy are immense.

On 05/10/2019 22:57, Emil Engler via bitcoin-dev wrote:
> Hello dear mailing list subscribers.
> Before I'll explain my idea here, I need to define a term first
> 
> 'address':
> When I use the terms address, pubkey, etc., I mean the same: The Base58
> string
> 
> Ok now let's get into it:
> As you should know, sending bitcoins to an address more than once is a
> very bad approach.
> In my opinion the problem why so many people are still doing this is
> because of the term 'address' which is used in lots of wallets,
> implementations, BIP 21 and so on. It is a design issue.
> With the term 'address' most people identify things that are fixed and
> don't change really often (e.g postal address, IP address [depends on
> provider], Domain, E-Mail address, ...).
> Because of this most people compare bitcoin addresses with e-mail
> addresses and use this address to send the recipient money multiple times.
> 
> My suggestion would be to change the term address in wallets, the URI
> scheme and so on to something of the following options by a
> Informational/Process BIP:
> 
> * Payment Password
> * Transaction Password
> * ...
> 
> The guideline for the term should indicate that it is:
> * temporary
> * Something that identifies the recipient
> 
> I've chosen 'password' because they can be used as a pseudonym to
> identify a person.
> This is already used in stuff like bank transfers where something like
> the transaction id should be used as the purpose or at universities
> there are student numbers.
> The first is probably a better example because student numbers aren't
> temporary.
> 
> What do you think? Should I write a BIP for this or use another term?
> Feedback is most welcome :)
> 
> Greetings,
> Emil Engler
> 
> 
> ___
> 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] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-08-08 Thread Chris Belcher via bitcoin-dev
Hello list,

Two points:

* The V^2 term is the only thing in the whole scheme that provides any
sybil protection. I've already gone through the reasoning in an earlier
email and the maths is clear; in a scheme with linear V honest makers
have no economic advantage over sybil attackers. This is because only a
sybil attacker needs to split up their money into multiple fidelity
bonds, and that comes with a penalty under the V^2 rule.

It's worth reiterating that including a single evil maker in a
JoinMarket coinjoin does not ruin it's privacy. Privacy is only ruined
if *all* makers in a coinjoin are controlled by the same entity. So if
takers use one maker who has rented TXOs, then its no big deal as long
as the other included makers are controlled by other people. Therefore
when balancing the harms, consolidation into fewer makers is not as bad
as having no sybil protection (which as a reminder means that *all*
makers are controlled by one entity), and so the V^2 term does more good
than harm.

We can't condemn the V^2 rule because of consolidation without
acknowledging the good it does in penalizing sybil attacks.

* Regarding entities like exchanges running makers. They can also do
this today with JoinMarket, the proposed fidelity bond scheme doesn't
make that worse. It's an underlying assumption of JoinMarket that
coinjoining power is proportional to bitcoin ownership (in a similar way
that an underlying assumption of bitcoin is that transaction
confirmation power is proportional to hashpower). If those big exchanges
find that coinjoins involving them included just one maker controlled by
someone else then their aim of deanonymization will have failed. And
then those exchanges have to explain to their regulators why they helped
hide the origin and destination of some black market money.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-08-07 Thread Chris Belcher via bitcoin-dev
These are very creative schemes. At the very least they would stop the
easy mindless renting TXO method, where someone with coins on a hardware
wallet simply creates a signature and copypastes it into a website to
get free money. The workaround scheme with shared ownership of TXOs
requires brand new wallets to be created and hodlers must trust the
wallets enough to move their coins and hold them there for a long time.

Requiring fidelity bond TXOs to be held in hot wallets can also be
beaten as a scheme for stopping renting, because the rentee can put
their coin private keys on an always-on raspberry pi which is connected
to the maker's computer and constantly ready to give out signatures. The
coins would be in hot wallets yet still be rented out. As above the
raspberry pi setup would be much more of a hassle than copypasting a
signature into a website, so it could still be worth doing.

I wonder if there's a cryptographic way to prove that muSig and 2P-ECDSA
have not been used to create a certain pubkey/signature.

On 06/08/2019 22:37, Dmitry Petukhov wrote:
> Unfortunately, both described schemes fail the same way as
> 'require TXOs to be consolidated by the owner', by the fact that with
> muSig, shared ownership of TXO is possible, as explained by ZmnSCPxj in
> [1]. 2P-ECDSA is also possible, just more complex, so just saying 'ban
> musig for the bonds' is not the answer, I believe.
> 
> [1]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017217.html
> 
> В Wed, 7 Aug 2019 01:55:41 +0500
> Dmitry Petukhov  wrote:
> 
>> В Mon, 5 Aug 2019 20:04:26 +0100
>> Chris Belcher  wrote:
>>
>>> So what's needed is a way to make renting out TXOs impossible or
>>> very difficult.  
>>
>> You can make renting the TXOs risky for the attacker. Make it so that
>> the entity that rented out the TXO can revoke the participation of
>> said TXO in the market, by publishing some special signature. That
>> act of revocation can also mean revocation of all other TXOs that
>> were used in a bond alongside it. This way, any entity that wants to
>> spoil an attacker's consolidation via rent, can rent out its TXO to
>> the attacker, and then revoke it, spoiling the whole package the
>> attacker have consolidated.
>>
>> There may be other way to impose penalties.
>>
>> For example, all locked TXO may be required to be spendable by *any*
>> key that controls any TXO in the 'bond TXO package'. I think this
>> should be possible with taproot - you will have to publish a taproot
>> trees for your locked TXOs (say, N of them), and the tree for each TXO
>> will have N leaves, each leaf will specify a condition "spendable by
>> the key N". This way, if I give you my TXO to include it in a bond by
>> locking it, you also need to make your other TXOs in a bond spendable
>> by me.
>>
>> For both scenarios to work for the attacker, there's need to be an
>> off-chain contractual relationship between the parties. Otherwise the
>> entity that rents out the TXOs can spoil or just confiscate the bond
>> of the entity that rented them, without reprecussions.
> 
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-08-07 Thread Chris Belcher via bitcoin-dev
On 07/08/2019 00:33, ZmnSCPxj wrote:
> Good morning all,
> 
> It might be useful to remember that there exists pressure to pool 
> proof-of-work due to tiny non-linearities caused by Proximity Premium and 
> Variance Discount flaws.
> Similarly, any non-linearity in any fidelity bond scheme exerts the same 
> pooling pressure.
> Deliberately increasing the non-linearity to V^2 worsens the pooling 
> pressure, not lessens it.
> 
> (I wonder if instead going the opposite way and doing V^0.999 might work 
> better; I have not figured all the implications of such a scheme and leave it 
> to the reader.)
> 
>> Unfortunately, both described schemes fail the same way as
>> 'require TXOs to be consolidated by the owner', by the fact that with
>> muSig, shared ownership of TXO is possible, as explained by ZmnSCPxj in
>> [1]. 2P-ECDSA is also possible, just more complex, so just saying 'ban
>> musig for the bonds' is not the answer, I believe.
> 
> If my understanding is correct, efforts to expand ECDSA to more than 
> two-party n-of-n "true" multisignatures already are ongoing.
> 
> One might attempt to use transaction malleability as a protection, and 
> require that transactions that put up bond TXOs should spend from at least 
> one ***non***-SegWit output, so that the scheme as described fails (as the 
> funding txid is malleable after-the-fact).
> 
> But the scheme as described only considers ways to securely aggregate 
> *within* the Bitcoin universe.
> 
> I have recently learned of a spacce called the "real world", wherein 
> apparently there exist things as "contract law".
> It seems to me this "contract law" is a half-baked implementation of Bitcoin 
> cryptographic smart contracts.
> By what little I understand of this "contract law", it would be possible for 
> an aggregator to accept some amount of money, with a promise to return that 
> money in the future with some additional funds.
> If the aggregator fails to uphold its promise, then some (admittedly 
> centralized) authority entity within the "real world" then imposes 
> punishments (apparently inspired by similar mechanisms in Lightning Network) 
> on the aggregator.
> Such arrangements (accepting some money now with a promise to return the 
> money, plus some interest earned, in the future) apparently already exist in 
> this "real world", under the name of "time deposits".
> 
> 
> Regards,
> ZmnSCPxj
> 

Good morning all,

Custodial solutions are much less worrying because they introduce so
much counterparty risk.

It's more risky to give bitcoins in custody than for fiat money because
there's no lender of last resort. People using JoinMarket in a
non-custodial way will always have a larger risk-adjusted return; The
return for running a JoinMarket yield generator isn't that big anyway to
start with. The non-custodial renting of TXO signatures is far more
worrying.

Also, as described in my other email
(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017218.html
starting "
Let's say the sybil attacker...") the superlinear V^2 term is essential
to the resistance of the fidelity bond system to sybil attacks. All
things considered the consolidation of makers due to renting TXOs is not
as bad as sybil attacks. Consolidation of makers means that the
privacy-relevant information is shared amongst fewer people than
otherwise, but at least those people are independent (otherwise they'd
merge together). In a sybil attack the privacy-relevant information is
not shared at all, but entirely known by just one person which is much
worse.

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


Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-08-06 Thread Chris Belcher via bitcoin-dev
On 06/08/2019 02:51, Leo Wandersleb via bitcoin-dev wrote:
> On 8/6/19 7:04 AM, Chris Belcher via bitcoin-dev wrote:
>> However, there _is_ a cost to being a sybil attacker. If we define
>> honest makers as entities who run just one maker bot, and dishonest
>> makers as entities who run multiple maker bots, then we can say that
>> running a dishonest maker operation requires a sacrifice of fee income,
>> because someone doing that would earn more money if they ran an honest
>> maker instead. This happens because of the quadratic V^2 term in the
>> formula calculating the fidelity bond value, which provides this
>> incentive for lumping together fidelity bonds. This V^2 is probably the
>> most important part for privacy.
> 
> As established above, there will emerge a market to lock coins, so these locks
> will be readily available without having to buy them. Even with V^2 there is 
> no
> reason to amass more coins beyond a certain point. Running the biggest 5 V^2
> scores should be pretty solid to get in on many coin joins.

We can be much more exact than saying makers get in on "many" coins. The
supporting document "Financial mathematics of JoinMarket fidelity bonds"
contains calculations for exactly this:
https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b#sybil-attacks-from-enemies-within

The document finds that with realistic real-world data, the makers with
the top 5 most valuable bonds will be chosen 48% of the time. So
approximately half:half success for one coinjoin. This isn't enough to
deanonymize every single coinjoin. For example, the tumbler script by
default makes around 16 transactions so the odds of a successful sybil
attack is (0.48)^16 = 8 parts per million, with the success probability
reducing exponentially after each additional coinjoin.

>> Another way is to require the bond signature proofs to involve the
>> one-time taker identifier, and so be different every time. This
>> basically requires fidelity bond privkeys to be online in hot wallets,
>> and so should massively increase the difficulty of renting TXOs because
>> the maker and the TXO owner need to be in constant real-time communication.
> 
> Requiring the bond to reside on a hot wallet would be a massive disadvantage.

Hopefully it won't come to that and we can invent some other way to stop
renting TXOs. But if that's the only way then we'd have to code it in
order to protect the interests of takers.

The most dangerous source of rented TXOs seems to be the coin age form
of fidelity bond. Hodlers could have coins already in a hardware wallet
or cold storage and just sign proofs renting their UTXOs to earn an
extra income without changing their setup at all. Bonds from OP_CLTV and
OP_RETURN burned coins seems to me a much less likely source of rented TXOs.

Because of that, it seems to me only coin age fidelity bonds would be
required to be on hot wallets.

Another option worth considering is the have a separate lower interest
rate for coin age bonds compared to OP_CLTV bonds, this would reflect
the lower sacrifice for coin age (past sacrifices must be worth less
than future sacrifices, because of risk and uncertainty of the unknown
future, as well as the risk of rented UTXOs)

> No matter how you look at the whole problem of sibyl attacks, the honest maker
> will have operational costs and gain fees and the sibyl attacker will have the
> same plus profit from the deanonymization. As long as makers hunt marginal
> profits, the sibyl attacker having the higher margin from deanonymization will
> always win. The fidelity bonds would make this even worse, as increased
> complexity and entry cost would not favor more makers but less even before the
> centralization incentive mentioned above (V^2). To say that old holders have
> bitcoins laying around that they can use for such bonds is a fallacy as they
> could just as well rent them out on a bonds market.

I think this is absolutely wrong, because sybil attackers give up some
fee income. Here is a worked example:

Let's say the sybil attacker is operating the top 5 most valuable maker
bots. If this attacker has X coins they would split them equally into 5,
so each maker has X/5 coins and their bond is worth (X^5)^2 = X^2/25,
with a total of 5 bots the fee income would be proportional to 5*X^2/25
= X^2/5. However if an honest maker had X coins they could create a
single bond which would be worth simply X^2 with a fee income
proportional to X^2. So the honest maker has a fee income higher by a
factor of 5 than the sybil attacker. The sybil attacker must take a 5x
hit to their fee income in order to sybil attack. This is the crucial
effect of the V^2 term.

The V^2 term is important, it just has the downside of incentivizing
renting of coins. If we can make that impossible then the problem would
go away.

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-08-05 Thread Chris Belcher via bitcoin-dev
On 02/08/2019 10:50, Dmitry Petukhov wrote:
> В Fri, 2 Aug 2019 10:21:57 +0100
> Chris Belcher  wrote:
> 
>> The aim of the fidelity bond scheme is to require makers
>> to sacrifice value, renting out their fidelity bond coins doesn't
>> avoid that sacrifice because the sacrifice is the paid rent
> 
> But if the entity that rented the coins, makes a profit using this coins
> from the maker opertion, and it makes the same or higher amount than
> it paid in rent, is it a sacrifice ? Given that the aim was to not make
> a profit in the first place, just increase deanonymization
> capabilities ?

Yes you're right. I should correct myself: Running a maker under the
proposal doesn't require a sacrifice of value, in fact you actually make
money doing it.

However, there _is_ a cost to being a sybil attacker. If we define
honest makers as entities who run just one maker bot, and dishonest
makers as entities who run multiple maker bots, then we can say that
running a dishonest maker operation requires a sacrifice of fee income,
because someone doing that would earn more money if they ran an honest
maker instead. This happens because of the quadratic V^2 term in the
formula calculating the fidelity bond value, which provides this
incentive for lumping together fidelity bonds. This V^2 is probably the
most important part for privacy.

The V^2 term also creates a bad incentive where multiple people might
choose to pool together their bitcoin hoard into one maker bot so that
each can earn a higher fee income. This can be done by renting out TXOs
signatures as you've said.

So what's needed is a way to make renting out TXOs impossible or very
difficult. We can note that fidelity bonds made of rented TXOs will be
made up of a large number of relatively small valued TXOs, so one
amelioration is to cap the number of TXOs that can be used in one
fidelity bond. This could be worked around by honest makers because they
can consolidate TXOs on the blockchain, which rented TXO owners can't do
because the TXOs are owned by different people.

Another way is to require the bond signature proofs to involve the
one-time taker identifier, and so be different every time. This
basically requires fidelity bond privkeys to be online in hot wallets,
and so should massively increase the difficulty of renting TXOs because
the maker and the TXO owner need to be in constant real-time communication.

Thoughts?

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


Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-08-02 Thread Chris Belcher via bitcoin-dev
On 31/07/2019 16:50, Dmitry Petukhov wrote:
> В Tue, 30 Jul 2019 22:39:14 +0100
> Chris Belcher via bitcoin-dev 
> wrote:
> 
>> This is where a sacrifice of V bitcoins creates a
>> bond of value V^2. The formula provides a strong incentive for
>> profit-motivated makers to use all their fidelity bond coins with just
>> one maker, not spread them out over many makers.
> 
> The attacker derives additional value from the use of
> locked utxo - the deanonimyzation capabilities.
> 
> An entity M can use all of its locked coins to run a maker, and then
> earn value X. It will also incur some operational expenses in the course
> of running the maker, so the profit will be less than X.
> 
> If these locked coins are given to the attacker A as a package, an
> attacker can derive a value of X+D where D is a value of increased
> deanonymization capabilities for an attacker. Operational expenses
> for an attacker are the same as before (without timelocked bonds),
> because they need to operate a lot of makers either way.
> 
> If M is profit-driven and non-ideological, it can rent out all of its
> coins to A as a package, for the price X, and get the same value without
> running a maker and dedicating any resources and time to it, not
> incurring any operatinal expenses (thus having a bigger profit in the
> end).
> 
> Attacker A will run a maker with M's coins, get profit X, pay X to M,
> get increased deanonymization capabilities. 
> 
> If renting out of utxo is done in a way that the owner always gets X
> after the lock expires, the operation will be riskless for the owner.
> The attacker will need to lock amount X along with owner's coins, but
> hopefully makes X back by running a maker operation. 
> 
> The price for renting out the coins will be determined on the size of
> the 'coin package', so it will not be feasible for the owners of the
> coins to rent them out separately.
> 
> An attacker can even rent coins from several entities and combine them
> to create a more 'powerful' maker. If I understand correctly, such
> 'powerful' maker can have bigger profit than two less 'powerful'
> makers. It seems like a centralization risk to me.
> 

There's a few different issues here.

Yes TXO fidelity bonds can be rented out, but that doesn't make a sybil
attack cheaper. The aim of the fidelity bond scheme is to require makers
to sacrifice value, renting out their fidelity bond coins doesn't avoid
that sacrifice because the sacrifice is the paid rent. Because of the
maths and market forces the rent paid by the attacker should be about
the same as the cost of just buying the bitcoins and locking them.

Centralization and decentralization are not ends in themselves, the main
aim in JoinMarket is to improve privacy while keeping the other
properties of bitcoin (e.g. censorship resistance). A single maker can
never deanonoymize coinjoins no matter how valuable their bond is,
because takers always choose multiple makers, and all of them need to be
controlled by the sybil attacker for the attack to succeed. If a sybil
attacker splits up their fidelity bonds (rented or not) amongst multiple
maker bots then they reduce the value of their bonds because of the V^2
term.

Rented TXOs does destroy the effect of "A long-term holder probably
won't want to attack a system like JoinMarket which makes his own
investment coins more private and more fungible". However this is not
the main effect which would protect JoinMarket's privacy. The main
effect is the cost which for real-life numbers would be about 45-120
bitcoin sent to burner outputs.

Perhaps then rented TXOs is an argument against using coin age as a way
to create fidelity bonds. Hodlers would be far less likely to rent out
their coins if they have to specifically move them to a special
time-locked address. Another point is that for privacy reasons creators
of fidelity bonds should mix their coins before and after using them,
because those TXOs are revealed to the world. So it's likely that
fidelity bonds creators will need to install and run JoinMarket anyway.

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


Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-07-31 Thread Chris Belcher via bitcoin-dev



On 26/07/2019 10:38, Dmitry Petukhov via bitcoin-dev wrote:
> 
> If the attacker is the entity who provides this 'maker outsourcing',
> and it captures significant portion of that maker-outsourcing/utxo-rent
> market, it can even receive some profit from the convenience fee, while
> deanonymizing the joins.
> 
> And with pseudonymous entities, you cannot be sure how much of that
> market the attacker controls.
> 

No the attacker does not. I believe renting out UTXO proofs does not
change the privacy properties, because of the quadratic term in the
fidelity bond formula. This is where a sacrifice of V bitcoins creates a
bond of value V^2. The formula provides a strong incentive for
profit-motivated makers to use all their fidelity bond coins with just
one maker, not spread them out over many makers. JoinMarket takers
always use multiple makers, so a single maker can never deanonymize a
coinjoin just they get chosen by takers a lot. (But they would make
loads of money in coinjoin fees, which should encourage other makers to
also sacrifice coins in order to compete with them and capture some of
that fee income)

If a sybil attacker wants to run multiple makers for the purpose of
deanomyization then they will take a substantial quadratic hit in their
effectiveness. This is explored the other document "Financial
mathematics of JoinMarket fidelity bonds"
https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b


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


Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-07-31 Thread Chris Belcher via bitcoin-dev
On 27/07/2019 20:34, David A. Harding wrote:
> 
> Timelocking bitcoins, especially for long periods, carries some special
> risks in Bitcoin:
> 
> 1. Inability to sell fork coins, also creating an inability to influence
> the price signals that help determine the outcome of chainsplits.
> 
> 2. Possible inability to transition to new security mechanisms if
> a major weakness is discovered in ECC or a hash function.
> 

Far future locks are problematic. In my proposal I've only considered
locked coins for only 6 months because of exactly these reasons. The
market competition between airdrops should still exist after 6 months so
lockers will still get a chance to sell their airdrops. And any
ECC-alternative or hash-function-alternative fork will probably take a
couple of months to be designed, implemented and deployed as well,
giving a chance for lockers to move coins.


> An alternative to timelocks might be coin age---the value of a UTXO
> multiplied by the time since that UTXO was confirmed.  Coin age may be
> even harder for an attacker to acquire given that it is a measure of
> past patience rather than future sacrifice.  It also doesn't require
> using any particular script and so is flexible no matter what policy the
> coin owner wants to use (especially if proof-of-funds signatures are
> generated using something like BIP322).

I'm becoming more and more convinced that coin age is also a valid
method of proving a sacrifice. Using coin age also has a benefit that
less block space is used, because using timelocks requires a new
on-chain transaction to be made every 6 months or whatever the locking
period is.

Perhaps JoinMarket should accept all three methods of proving a
sacrifice: burning, timelocking and aging. I could imagine that makers
would first lock coins for 6 months to create a fidelity bond they could
immediately use, and after the timelock expires leave that coin unspent
and use its age as the fidelity bond.

For what its worth, I mostly considered burning coins because the maths
for it is easy (the value of such a bond is just V^2), and because it
provides a boundary condition (locking up coins for infinity time is the
same as burning them). I doubt anybody will actually do it in practice.


> - BIP158 users who have saved their past filters to disk can use them to
>   determine which blocks subsequent to the one including the UTXO may
>   contain a spend from it.  However, since a UTXO can be spent in the
>   same block, they'd always need to download the block containing the
>   UTXO (alternatively, the script could contain a 1-block CSV delay
>   ensuring any spend occurred in a later block).  If BIP158 filters
>   become committed at some point, this mechanism is upgraded to SPV-level
>   security.

This scheme could be attacked using address reuse. An attacker could
create an aged coin on a heavily-reused address, which would force an
SPV client using this scheme to download all the blocks which contain
this reused address which could result in many gigabytes of extra
download requirement.

So to fix this: a condition for aged coins is that their address has not
been reused, if the coin is on a reused address then the value of the
fidelity bond becomes zero.


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


[bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

2019-07-25 Thread Chris Belcher via bitcoin-dev
JoinMarket[1] can be sybil attacked today at relatively low cost which
can destroy its privacy. Bitcoins can be sacrificed with burner outputs
and time-locked addresses (also called fidelity bonds), and this can be
used to greatly improve JoinMarket's resistance to sybil attacks.

With real-world data and realistic assumptions we calculate that under
such a fidelity bond system an adversary would need to lock up
30,000-80,000 bitcoins for months, or send 45-120 bitcoins to burner
addresses to have a good chance of sybil attacking the system if it were
added to JoinMarket.

This increased resistance to sybil attacks would most likely cause
coinjoin fees to rise. I think the added cost is worth it for the
greatly improved privacy, because today miner fees are the biggest cost
to JoinMarket takers not coinjoin fees which are very low. Users should
definitely share their opinion on fees after reading the document.

## Introduction

JoinMarket creates a market for coinjoins, allowing anyone to create
equal-amount coinjoins for any amount they want at any time they want.
In return they pay a fee for the liquidity made available to them. The
project has existed since 2015 and has probably created hundreds of
thousands of coinjoins since then. Today there is available liquidity
for creating coinjoins with amounts up to about 400 btc per coinjoin output.

### Sybil attacks

JoinMarket, like many other schemes where participants are free to
anonymously enter, can be targetted by sybil attacks. In JoinMarket this
would work by an attacker running lots of maker bots which attempt to be
all the makers in every coinjoin. If successful the attacker would have
enough information unmix every coinjoin.

One way to solve the problem of sybil attacks is centralization. For
example coinjoins could be constructed on a centralized server. Then
random anonymous participants cant sybil attack because they can't
control the coinjoin construction, but this comes at the cost that the
server can sybil attack very easily. So this solution is probably a bad
tradeoff.

In general, sybil attacks are solved by making them expensive. For
example, bitcoin mining resists sybil attacks because it requires a
provable sacrifice of electricity to mine. A bitcoin user can calculate
the actual monetary value that an attacker must spend in order to
reverse their transaction.

Likewise in JoinMarket such a sybil attack is not free either as the
attacker needs to own enough bitcoins to run enough maker bots for all
the coinjoins.

### Today's low cost for sybil attacks

A paper on JoinMarket [Möser, Malte and Rainer Böhme. “Join Me on a
Market for Anonymity.” (2016).] calculates the requirement of such a
sybil attack in 2016 to be just 32,000 USD. According to the paper such
an attack would succeed 90% of the time and the investment is
recoverable afterwards so that figure for the requirement isn't even a
true cost.

JoinMarket has been improved since 2016 and more makers have joined, so
the true requirement is perhaps 2x or 3x higher today, but it is still
relatively low.

Even with future improvements like fixing issue #693 [2] the requirement
of a sybil attack would probably only rise another 2x.

Apart from the cost to sybil attack being low, there is also the odd
situation that smaller coinjoin amounts receive less sybil protection
than large ones. It costs 100x less to sybil attack a transaction of 0.1
btc than one of 10 btc. Why should smaller amounts receive less
sybil-resistance and therefore less privacy?

### Liquidity

When creating this project, it was expected that many more people would
enter the market as makers and so the cost of a sybil attack would be
very high. That has not happened. One reason is that everyone who wants
to create a coinjoin is able to even for large amounts. The fundamental
problem is that takers are paying-for and getting liquidity, but not
necessarily sybil-resistance.

Another smaller reason for the low cost of sybil attacks is that many
people don't want to store too many bitcoins on an computer connected to
the internet.

What is needed is a way to increase the cost of running in a maker in a
way that retains the anonymity and is attractive to long-term holders of
bitcoin. This can be done using time-locked addresses.

## Fidelity bonds

In bitcoin, a fidelity bond [3] is a mechanism where bitcoin value is
deliberately sacrificed to make a cryptographic identity expensive to
obtain. The sacrifice is done in a way that can be proven to a third party.

A way to create a fidelity bond is to burn an amount of bitcoins by
sending to a OP_RETURN output. Another kind is time-locked addresses
created using OP_CHECKLOCKTIMEVERIFY where the valuable thing being
sacrificed is time rather than money, but the two are related because of
the time-value-of-money.

Under this system, makers would sacrifice an amount of bitcoins and
publish a proof along with their coinjoin offers. Takers would choose
maker offers based on 

[bitcoin-dev] Privacy literature review

2019-03-05 Thread Chris Belcher via bitcoin-dev
Hello list,

For the last few weeks I've been working on a literature review for
bitcoin privacy:

https://en.bitcoin.it/wiki/Privacy

It aims to cover about all privacy issues in bitcoin, including
Lightning network, and has a bunch of examples to help demonstrate how
the concepts work in practice.

There is also a new wiki category with smaller related articles:

https://en.bitcoin.it/wiki/Category:Privacy

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


Re: [bitcoin-dev] Transaction Input/Output Sorting

2018-10-24 Thread Chris Belcher via bitcoin-dev
Thanks for bringing our attention to this important topic.

According to (https://p2sh.info/dashboard/db/bip-69-stats) around 60% of
transaction follow bip69 (possibly just by chance).

If its useful, a bitcoin wiki page that tracks wallets which use bip69
can be created. A similar page exists for bech32
(https://en.bitcoin.it/wiki/Bech32_adoption). If we had this at least
we'd know which open source wallets we can write code for or which
closed source wallets we can bug about bip69.


On 22/10/2018 02:54, Ryan Havar via bitcoin-dev wrote:
> On Sunday, October 21, 2018 2:54 PM, Pavol Rusnak  
> wrote:
> 
>> Your solution in the second part of the email does not solve the problem you 
>> indicated in the first part of your email.
> 
> Sorry, I'm not quite sure what parts you are referring to. I assume you might 
> mean my first paragraph, so I'll try explain myself a bit clearer how this 
> makes it harder to find wallet boundaries.
> 
> Right now you can generally tell if a transaction is using bip69 or not (as 
> long as you account for the probability that it's randomly sorted to 
> accidentally be bip69). And generally wallets are consistent if they use 
> bip69 or not.
> 
> This can often make it massively easier to detect what is change and not. 
> Let's say I'm clustering a wallet and know they're using a wallet that always 
> uses bip69, and I'm looking at a transaction in that cluster and trying to 
> guess which is the change and which is not. There's a lot of things you can 
> use to assign a probability. The most obvious thing is looking at the amount 
> of significant-digits of the output amounts  (if they vary a lot, change 
> tends to be the one with more), but a much more powerful one is looking at 
> how the outputs are spent (and if they end up spend-linking back into the 
> original cluster).
> 
> So let's say that the transaction output is spent by a non-bip69 transaction 
> -- I right away know that it's going to (almost certainly) be a different 
> wallet (e.g. the destination).
> 
> My  (shower-thoughty) "solution" fixes this problem, because an outside 
> observer has no way of knowing if a transaction is using deterministic 
> sorting or not, so can not use this information to establish wallet 
> boundaries.
> 
> --
> On somewhat of a tangent I was actually fortunate enough to have someone with 
> access to the biggest(?) bitcoin analysis service help me with a few 
> experiments. While I was genuinely taken aback by how accurate some of their 
> analysis can be, I also found it pretty easy to trick -- implying it relies 
> heavily on some fragile heuristics.
> 
> I don't like to be alarmist, but I worry a lot about the fungibility of 
> bitcoin when we have such effective blockchain analysis and a *LOT* of the 
> ecosystem using a centralized analytics service. And in fact, we're already 
> starting to see some minor effects of this (e.g. people already know that if 
> they gamble their funds, they'll probably have trouble using an exchange 
> later). And I don't think we're too far from the point where any 
> "unidentified" bitcoin is instantly flagged as "suspicious" (and for 
> instance, requires more explaining for by exchanges) potentially seriously 
> harming bitcoin fungibility and it's value determined also by it's history.
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


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

2018-05-10 Thread Chris Belcher via bitcoin-dev
Thanks for the summary,

It may be worth emphasizing the fungibility aspects of all this.

That summary contains ideas to possibly have separate address types,
opcodes and scriptSigs/witnesses for different feature, at least to
start with. To me this would seem bad because it may miss out on the
fungibility gain from having everything look exactly the same.

With schnorr we may have a unique opportunity to greatly improve
fungibility. It's not too hard to imagine a world where users of
Lightning Network, coinswap, MAST, scriptless scripts, multisig,
taproot, graftroot, etc and regular single-signature on-chain payments
all appear completely indistinguishable. Tracking and data mining could
become pointless when coins can teleport undetectably to a different
place on the blockchain via any number of off-chain protocols.

Of course the downside of doing it like this is that every feature would
probably have to be developed, reviewed, tested and deployed together,
rather than one at a time.

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

[bitcoin-dev] Electrum Personal Server beta release

2018-03-29 Thread Chris Belcher via bitcoin-dev
Electrum Personal Server is an implementation of the Electrum wallet
server protocol that allows users to point their Electrum wallet at
their own full node. It is compatible resource-saving features like
pruning, blocksonly and disabled txindex. It is much less
resource-intensive than other Electrum servers because it only stores
the user's own addresses, instead of every address that was ever used.
As such it makes tradeoffs, namely losing Electrum's "instant on" feature.

Right now using Electrum Personal Server is the easiest way to use a
hardware wallet backed by your own full node. It is very lightweight,
being a small python script that barely uses any CPU or RAM; much less
than the full node it's connected to. Hopefully Electrum Personal Server
can be part of the solution in putting full node wallets into the hands
of as many people as possible.

The project is now in beta release:
https://github.com/chris-belcher/electrum-personal-server

It now has all the essential features to make it practical for use;
Merkle proofs, deterministic wallets, bech32 addresses, SSL, Core's
multi-wallet support. Along with the features that were in the alpha
release of tracking new transactions, confirmations, block headers,
importing addresses.

There is a caveat about pruning. Electrum Personal Server obtains merkle
proofs using the `gettxoutproof` RPC call, if pruning is enabled and
that block has been deleted then the RPC will return null and so the
Electrum wallet will display `Not Verified`. Everything else will still
work, and this shouldn't be a problem in most situations because
Electrum usually only requests merkle proofs for recent transactions and
pruning keeps recent blocks. But in the long term it needs some thought
on the best way to fix this. I've been thinking about adding code for
Bitcoin Core that stores merkle proofs for each of the wallet's own
transactions in wallet.dat.

Further Reading:
*
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015707.html
* https://bitcointalk.org/index.php?topic=3167572.0
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

2018-01-22 Thread Chris Belcher via bitcoin-dev
This sounds like a useful idea for improving the privacy of coinswap.
Traditionally coinswap mixing had an anonymity set related to the number
of multisig transactions being used on the blockchain. With the new tech
of Schnorr, MAST and now this Taproot, with sufficient adoption
coinswap's anonymity set could be much higher, potentially including
almost every other on-chain transaction.

[1] https://bitcointalk.org/index.php?topic=321228.0
[2] https://github.com/AdamISZ/CoinSwapCS

On 23/01/18 00:30, Gregory Maxwell via bitcoin-dev wrote:
> Interest in merkelized scriptPubKeys (e.g. MAST) is driven by two main
> areas: efficiency and privacy. Efficiency because unexecuted forks of
> a script can avoid ever hitting the chain, and privacy because hiding
> unexecuted code leaves scripts indistinguishable to the extent that
> their only differences are in the unexecuted parts.
> 
> As Mark Friedenbach and others have pointed out before it is almost
> always the case that interesting scripts have a logical top level
> branch which allows satisfaction of the contract with nothing other
> than a signature by all parties.  Other branches would only be used
> where some participant is failing to cooperate. More strongly stated,
> I believe that _any_ contract with a fixed finite participant set
> upfront can be and should be represented as an OR between an N-of-N
> and whatever more complex contract you might want to represent.
> 
> One point that comes up while talking about merkelized scripts is can
> we go about making fancier contract use cases as indistinguishable as
> possible from the most common and boring payments. Otherwise, if the
> anonymity set of fancy usage is only other fancy usage it may not be
> very large in practice. One suggestion has been that ordinary
> checksig-only scripts should include a dummy branch for the rest of
> the tree (e.g. a random value hash), making it look like there are
> potentially alternative rules when there aren't really.  The negative
> side of this is an additional 32-byte overhead for the overwhelmingly
> common case which doesn't need it.  I think the privacy gains are
> worth doing such a thing, but different people reason differently
> about these trade-offs.
> 
> It turns out, however, that there is no need to make a trade-off.  The
> special case of a top level "threshold-signature OR
> arbitrary-conditions" can be made indistinguishable from a normal
> one-party signature, with no overhead at all, with a special
> delegating CHECKSIG which I call Taproot.
> 
> Let's say we want to create a coin that can be redeemed by either
> Alice && Bob   or by CSV-timelock && Bob.
> 
> Alice has public A, Bob has pubkey B.
> 
> We compute the 2-of-2 aggregate key C = A + B.  (Simplified; to
> protect against rogue key attacks you may want to use the MuSig key
> aggregation function [1])
> 
> We form our timelock script S =  " OP_CSV OP_DROP B 
> OP_CHECKSIGVERIFY"
> 
> Now we tweak C to produce P which is the key we'll publish: P = C + H(C||S)G.
> 
> (This is the attack hardened pay-to-contract construction described in [2])
> 
> Then we pay to a scriptPubKey of [Taproot supporting version] [EC point P].
> 
> Now Alice and Bob-- assuming they are both online and agree about the
> resolution of their contract-- can jointly form a 2 of 2 signature for
> P, and spend as if it were a payment to a single party (one of them
> just needs to add H(C||S) to their private key).
> 
> Alternatively, the Taproot consensus rules would allow this script to
> be satisfied by someone who provides the network with C (the original
> combined pubkey), S, and does whatever S requires-- e.g. passes the
> CSV check and provides Bob's signature. With this information the
> network can verify that C + H(C||S) == P.
> 
> So in the all-sign case there is zero overhead; and no one can tell
> that the contract alternative exists. In the alternative redemption
> branch the only overhead is revealing the original combined pubkey
> and, of course, the existence of the contract is made public.
> 
> This composes just fine with whatever other merkelized script system
> we might care to use, as the S can be whatever kind of data we want,
> including the root of some tree.
> 
> My example shows 2-of-2 but it works the same for any number of
> participants (and with setup interaction any threshold of
> participants, so long as you don't mind an inability to tell which
> members signed off).
> 
> The verification computational complexity of signature path is
> obviously the same as any other plain signature (since its
> indistinguishable). Verification of the branch redemption requires a
> hash and a multiplication with a constant point which is strictly more
> efficient than a signature verification and could be efficiently fused
> into batch signature validation.
> 
> The nearest competitor to this idea that I can come up with would
> supporting a simple delegation where the output can be spent by the
> 

[bitcoin-dev] Payment Channel Payouts: An Idea for Improving P2Pool Scalability

2017-08-30 Thread Chris Belcher via bitcoin-dev
Pooled mining in bitcoin contributes to miner centralization. P2Pool is
one solution but has bad scalability; additional hashers require the
coinbase transaction to be larger, bigger miners joining increase the
variance of payouts for everyone else, and smaller miners must pay extra
to consolidate dust payouts. In this email I propose an improved scheme
using payment channels which would allow far more individual hashers to
mine on p2pool and result in a much lower payout variance.


== Intro ==

P2Pool is a decentralized pool that works by creating a P2P network of
hashers. These hashers work on a chain of shares similar to Bitcoin's
blockchain. Each hasher works on a block that includes payouts to the
previous shares' owners and the node itself. The point of pooling is to
reduce the variance of payout, even though on average the reward is the
same (or less with fees). The demand for insurance, and the liquid
markets for options show that variance does have costs that people are
willing to pay to avoid.

Here is an example of a p2pool coinbase transaction:
https://blockchain.info/tx/d1a1e125ed332483b6e8e2f128581efc397582fe4c950dc48fadbc0ea4008022

It is 5803 bytes in size, which at a fee rate of 350 sat/b is worth
0.02031050 btc of block space that p2pool cannot sell to any other
transaction. As bitcoin inflation goes down and miners are funded more
by fees, this puts p2pool at more and more of a disadvantage compared to
trusted-third-party mining pools.

As each hasher is paid to their own bitcoin address, this limits the
number of hashers taking part as adding more individual people to the
payout transaction increases its size. Also small payouts cost a
disproportionate amount in miner fees to actually spend, which hurts
small miners who are essential to a decentralized mining ecosystem.

This could maybe be solved by keeping a separate balance state for each
user that is independent from the payouts, and make payouts only when
that balance state exceeds some reasonable threshold. But this increases
the variance which goes against the aim of pooled mining.


== Payment Channels ==

What's needed is a way to use off-chain payments where any number of
payments can be sent to each individual hasher without using the
blockchain. Then the N of the pay-per-last-N-shares (PPLNS) of p2pool
can be increased to something like 6-12 months of shares and so as long
as a small miner can mine a share every few months they will always get
a payout when p2pool finds a block. The payment channels would be in a
hub-and-spokes system and would work in a similar way to coinswap,
lightning network, atomic cross-chain swaps or any other contract
involving hashlocks and timelocks.

There would still be a sharechain but with hashers paying the entire
block reward to a hub. This hub would have a one-way payment channel
open to every hasher in p2pool and there would be created a situation
where if the hub gets paid then the hashers cannot fail to get paid.
Because cheating is impossible, the hub and hashers will agree to just
release the money to each other without resorting to the blockchain.

The coinbase address scriptPubKey would be this, block rewards are paid
to here:

 2of2 multisig
 hub + successful hasher
  OR
 hub pubkey + H(X)
  OR
 successful hasher pubkey + OP_CSV 6 months

A 2of2 multisig between the hub and the "successful" hasher which found
the block, although with a hashlock and timelock. H(X) is a hash value,
where the preimage X is generated randomly by the hub and kept secret,
but X will be revealed if the hub spends via that execution path. The
OP_CSV execution path is there to stop any holdups or ransom, in the
worst case if the hub stalls then the successful hasher can steal the
entire coinbase as punishment after 6 months.

Each payment channel address has this scriptPubKey:

 2of2 multisig
 hub-C + hasher-C
  OR
 2of2 multisig + H(X)
 hub-U + hasher-U

The pubkeys hub-C/hasher-C refer to 'cooperative' pubkeys.
Hub-U/hasher-U refer to 'uncooperative' pubkeys. Before a hasher starts
mining the hub will open a one-way payment channel to the hasher, and
pays some bitcoin to it (let's say 0.5btc for example).

The hashers mine a sharechain, a solved share contains the hasher's
cooperative and uncooperative pubkey. The hub keeps up with the
sharechain and announces partially-signed transactions going to each
hasher. The transactions are updated states of the payment channel, they
pay money to each hasher in proportion to the work that the hasher
contributed to the sharechain. The transaction contains a signature
matching the hub-U pubkey, the hasher could sign it with their hasher-U
key and broadcast except they still need the value of X.

If a hasher is successful and finds a share that is also a valid bitcoin
block, they broadcast it to the network.

Now, the hub can spend the block reward money on its own but only by
revealing X. Each hasher could then take that X and 

Re: [bitcoin-dev] Moving towards user activated soft fork activation

2017-03-05 Thread Chris Belcher via bitcoin-dev
I think UASF is a great idea for the reasons mentioned before that it
more closely matches the balance of powers in bitcoin, and that its much
more opt-in.

Many people are comparing an UASF fork with a hard fork. I disagree with
this view and I think there is a difference between the two kinds of
forks. The situation between hard and soft forks is reversed.

In a fork between segwit-invalid and segwit-valid after a UASF, if the
segwit-valid chain ever ends up with more work then the segwit-invalid
chain will be annihilated in a big re-organization as
non-segwit-enforcing nodes move to the segwit-valid chain. The less-work
chain will simply cease to exist.

Only a miner that recodes their software can initiate such a fork,
because segwit transactions are non-standard and won't be relayed by
default.

A closer situation is the accidental fork created soon after the BIP66
soft fork. The fork lasted a few blocks and did not mine any
transactions except the coinbase. It was annihilated with a monetary
loss to any miner that took part.


Here is an argument for why chain fork is unlikely to last long or be
created by a rational self-interested miner, assuming the bitcoin
economic majority even slightly enforces the UASF.

Because the segwit-invalid coins can be annihilated in this way and
segwit-valid coins cannot, segwit-invalid coins are more risky to hold
as an asset, all else equal.

A more risky asset has a lower price, all else equal. Because investors
demand higher risk premiums for holding it and also short sellers may
sell down the price in the hopes of making a profit if it's value goes
to zero.

In cryptocurrencies like bitcoin, hashpower follows price. This is very
clear from historical trends and the underlying economic forces.

A lower-hashrate chain will eventually be overtaken in work by a
higher-hashrate chain.

Therefore, the segwit-invalid chain will be annihilated sooner or later
if the price of its coin is higher.

Of course as the old saying goes markets can stay irrational longer than
we can stay solvent, which is why I think UASF should only go ahead if
we're sure that a big part of the economic majority will enforce it.
This will make the value and liquidity of the segwit-invalid chain very
low and make the annihilating re-organization happen faster.
User-activated means it _must_ be done by the users of bitcoin.

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


Re: [bitcoin-dev] Committed bloom filters for improved wallet performance and SPV security

2017-02-16 Thread Chris Belcher via bitcoin-dev
I believe this proposal still suffers from one problem that bip37 did,
albiet by a much lesser extent. Combining the partial information from
the block downloads with the transaction subgraph information from the
blockchain can in some cases still reveal which addresses belong to the
wallet. Nonetheless this proposal still has many benefits and is well
worth working on.

==BIP37==

As a recap, probably the biggest and most problematic way that bip37 was
broken was by combining the partial wallet information from the bloom
filter with the transaction subgraph information from the blockchain

Suppose a wallet synchronizes it's history, if it spent a coin from its
address A, it must also also add the change address B to the bloom
filter, which is connected to A directly on transaction graph.

As an example, consider five typical transactions that consume one input
each and produce two outputs.
A, B, C, D, E refer to transactions. A1, A2, etc refer to addresses
within those transactions

  -> C1
A1 -> B2  -> C2
   -> B2  -> D1
  -> D2 -> E1
-> E2

If a bip37 bloom filter matches addresses A1, B2, D2, E1 then it can be
seen that they form a "peel chain" [this terminology comes from
https://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf]

  -> X
A1 -> X   -> X
   -> B2  -> X
  -> D2 -> E1
-> X

The same five transactions with non-matching addresses replaced by X.
The peel chain is visible, it's clear that B2, D2, E1 are change
addresses which belong to the same wallet as A1.

For a given false-positive rate fp and given length of peel chain C, the
odds of a false positive peel chain happening by chance is fp^C which
rapidly gets very small as the wallet makes more transactions (increases C).

If only one address was matched from the above group (for example B2)
then it likely to be a false positive by the fact that it doesn't make
any transactions to another address that also matches the bloom filter.
Another possibility is that the address is a payment output that the
wallet received but hasn't spent yet, but the wallet cant spend it
without adding the change address to the bloom filter and thus revealing
itself to the spy.

I believe the committed bloom filter proposal is vulnerability to this
same kind of attack because it still leaks information about which
addresses the wallet is interested in.

==Committed Bloom Filter Maths==

I'll try to analyze this now. I'll find the expectation value of the
number of transaction subgraphs in those blocks that appear just by
chance. If this expectation goes to zero, then the only transaction
subgraph left will be the real one that the wallet is actually
interested in. In that case it will be possible to spy on the wallet.

Assuming outputs have the same probability of being spent in each time
interval (i.e. they are spent in a Poisson process) This is
approximately true, see the graphs from
[https://letstalkbitcoin.com/blog/post/rise-of-the-zombie-bitcoins].
This means we can assign
a single probability P that an output is spent in each block.

Assume every transaction has one change address only and spending of
unconfirmed change doesn't happen (its more efficient to use RBF to add
additional outputs anyway)

Number of transactions per block = Q (about 1800 today)
Number of outputs per block = Z = 2*Q (approximately)
Length of peel chain = Number of transactions in wallet = C
Average time an output is unspent for = T (about 1 month, very roughly
estimating from the above blog post)
Probability an output being spent in any particular later block = P =
10minutes/T

Assume no false positive blocks
Say wallet downloaded two blocks and they are ordered by block height
The expected number of tx subgraphs between them, E(#G)
E(#G) = number of outputs created in block 1 that get spent in block 2
  = Z*P

Say the wallet downloaded three blocks
Expected number of subgraphs going through them all
E(#G) = number of outputs created in block 1 get spent in block 2, that
create a change address which gets spent in block 3
  = Z*P*P

Say the wallet downloaded C blocks
Expected number of tx subgraphs going through all the blocks by chance
E(#G) = Z*P^C
which gets small quickly as C goes up, because P < 1

Now drop the assumption about no false positive blocks.

Let the number of candidate blocks be D.
This is how many blocks the wallet scans, it's related to how far in the
past the wallet's keys was created. At one extreme wallet was created at
genesis block and so D = ~45, at other extreme created now so D = 0.
Note that D = 0 must also imply C = 0

Expected number of false positive blocks downloaded = F = fp*D

In all these situations the blocks are sorted by block height

Suppose have C=2, F=1, and false one is in the middle.
I want to find E(#G|CF), the expected number of transaction subgraphs
that appear just by chance, given C and F.
E(#G|CF) = how many outputs which are created in block 1 get spent in

Re: [bitcoin-dev] Start time for BIP141 (segwit)

2016-10-16 Thread Chris Belcher via bitcoin-dev
Hello,

Excellent news that segregated witness is nearing release for the mainnet.

I know I don't only speak for myself in saying that this has been
eagerly awaited for some time.

For the timing, I'd support segwit being usable on the network as soon
as is technically and safely possible.

We at JoinMarket are very interested in eventually using schnorr which
would allow signature aggregation and so reduce the cost of coinjoins.

Chris Belcher

On 16/10/16 15:31, Pieter Wuille via bitcoin-dev wrote:
> Hello all,
> 
> We're getting ready for Bitcoin Core's 0.13.1 release - the first one
> to include segregated witness (BIP 141, 143, 144, 145) for Bitcoin
> mainnet, after being extensively tested on testnet and in other
> software. Following the BIP9 recommendation [1] to set the versionbits
> start time a month in the future and discussion in the last IRC
> meeting [2], I propose we set BIP 141's start time to November 15,
> 2016, 0:00 UTC (unix time 1479168000).
> 
> Note that this is just a lower bound on the time when the versionbits
> signalling can begin. Activation on the network requires:
> (1) This date to pass
> (2) A full retarget window of 2016 blocks with 95% signalling the
> version bit (bit 1 for BIP141)
> (3) A fallow period consisting of another 2016 blocks.
> 
>   [1] https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki
>   [2] 
> http://www.erisian.com.au/meetbot/bitcoin-core-dev/2016/bitcoin-core-dev.2016-10-13-19.04.log.html
> 
> Cheers,
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Clearing up some misconceptions about full nodes

2016-02-10 Thread Chris Belcher via bitcoin-dev
I've been asked to post this to this mailing list too. It's time to
clear up some misconceptions floating around about full nodes.

=== Myth: There are only about 5500 full nodes worldwide ===

This number comes from this and similar sites: https://bitnodes.21.co/
and it measured by trying to probe every nodes on their open ports.

Problem is, not all nodes actually have open ports that can be probed.
Either because they are behind firewalls or because their users have
configured them to not listen for connections.

Nobody knows how many full nodes there are, since many people don't know
how to forward ports behind a firewall, and bandwidth can be costly, its
quite likely that the number of nodes with closed ports is at least
another several thousand.

Nodes with open ports are able to upload blocks to new full nodes. In
all other ways they are the same as nodes with closed ports. But because
open-port-nodes can be measured and closed-port-nodes cannot, some
members of the bitcoin community have been mistaken into believing that
open-port-nodes are that matters.

=== Myth: This number of nodes matters and/or is too low. ===

Nodes with open ports are useful to the bitcoin network because they
help bootstrap new nodes by uploading historical blocks, they are a
measure of bandwidth capacity. Right now there is no shortage of
bandwidth capacity, and if there was it could be easily added by renting
cloud servers.

The problem is not bandwidth or connections, but trust, security and
privacy. Let me explain.

Full nodes are able to check that all of bitcoin's rules are being
followed. Rules like following the inflation schedule, no double
spending, no spending of coins that don't belong to the holder of the
private key and all the other rules required to make bitcoin work (e.g.
difficulty)

Full nodes are what make bitcoin trustless. No longer do you have to
trust a financial institution like a bank or paypal, you can simply run
software on your own computer. To put simply, the only node that matters
is the one you use.

=== Myth: There is no incentive to run nodes, the network relies on
altruism ===

It is very much in the individual bitcoin's users rational self interest
to run a full node and use it as their wallet.

Using a full node as your wallet is the only way to know for sure that
none of bitcoin's rules have been broken. Rules like no coins were spent
not belonging to the owner, that no coins were spent twice, that no
inflation happens outside of the schedule and that all the rules needed
to make the system work are followed  (e.g. difficulty.) All other kinds
of wallet involve trusting a third party server.

All these checks done by full nodes also increase the security. There
are many attacks possible against lightweight wallets that do not affect
full node wallets.

This is not just mindless paranoia, there have been real world examples
where full node users were unaffected by turmoil in the rest of the
bitcoin ecosystem. The 4th July 2015 accidental chain fork effected many
kinds of wallets. Here is the wiki page on this event
https://en.bitcoin.it/wiki/July_2015_chain_forks#Wallet_Advice

Notice how updated node software was completely unaffected by the fork.
All other wallets required either extra confirmations or checking that
the third-party institution was running the correct version.

Full nodes wallets are also currently the most private way to use
Bitcoin, with nobody else learning which bitcoin addresses belong to
you. All other lightweight wallets leak information about which
addresses are yours because they must query third-party servers. The
Electrum servers will know which addresses belong to you and can link
them together. Despite bloom filtering, lightweight wallets based on
BitcoinJ do not provide much privacy against nodes who connected
directly to the wallet or wiretappers.

For many use cases, such privacy may not be required. But an important
reason to run a full node and use it as a wallet is to get the full
privacy benefits.

=== Myth: I can just set up a node on a cloud server instance and leave
it ===

To get the benefits of running a full node, you must use it as your
wallet, preferably on hardware you control.

Most people who do this do not use a full node as their wallet.
Unfortunately because Bitcoin has a similar name to Bittorrent, some
people believe that upload capacity is the most important thing for a
healthy network. As I've explained above: bandwidth and connections are
not a problem today, trust, security and privacy are.

=== Myth: Running a full node is not recommended, most people should use
a lightweight client ===

This was common advice in 2012, but since then the full node software
has vastly improved in terms of user experience.

If you cannot spare the disk space to store the blockchain, you can
enable pruning as in:
https://bitcoin.org/en/release/v0.11.0#block-file-pruning. In Bitcoin
Core 0.12, pruning being enabled will leave the wallet enabled.