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

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

[Chris Belcher]

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 the sacrificed amount (as well as other factors),
knowing that a sybil attacker would also have to sacrifice a certain
amount of coins in order to unmix the taker's coinjoins. The sacrifice
would be an objective measurement that can't be faked and which can be
verified by anybody (just like, for example PoW mining)

Note that a long-term holder (or hodler) of bitcoins can buy time-locked
fidelity bonds essentially for free, assuming they never intended to
transact with their coins much anyway. 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.

### Fidelity bonds in cold storage

The private keys of fidelity bonds can be kept offline. Signatures
potentially only need to be made when the timelock expires (every 6
months for example), or only once in the case of OP_RETURN burned coins.
This allows JoinMarket's sybil resistance to increase without the hot
wallet risk.

Burned coin signatures should still have a lifetime, in case the private
key associated with the IRC nick (which is online) is stolen, so that
the thief of that privkey can't impersonate the maker indefinitely. The
signature linking the burned coins and IRC nick could expire after
perhaps 6 months.

### Anonymity

Under this scheme makers would need to publish the transactions of their
fidelity bonds to the entire world. Those transactions could be subject
to blockchain analysis. So before makers do this they should make sure
their coins are anonymous (possibly by mixing with JoinMarket). Also if
they ever want to use their coins for something else apart from fidelity
bonds they should mix them.

### Value of a fidelity bond

See the other document (Financial mathematics of joinmarket fidelity
bonds)[4] for a formula expressing the value of a fidelity bond.

The value of a fidelity bond made by sending V bitcoins to a burner
address is:

    V^2

The amount of bitcoins is squared to get the fidelity bond value. This
has the effect that economic-rational makers have a strong incentive to
lump up all their coin sacrifices together into one maker bot, not to
split it up over several bots.

The value of a fidelity bond made by locking up V bitcoins in a
time-locked address for time period T is:

    V^2 (exp(rT) - 1)^2

To get an idea of the numbers, if we burn 2 btc then the value of the
fidelity bond is 4 BTC^2. If we lock up 100 BTC for one year, and have a
bitcoin interest rate r = 0.001 (0.1%) per year, then the value of that
fidelity bond is 0.01 BTC^2 which is the same as burning 0.1 BTC. That
is a relatively small valued bond. It can be increased by locking up
more bitcoins for longer (up to and including permanant locking via a
burner transaction).

## Taker algorithm for choosing makers

I suggest the following taker peer choosing algorithm: obtain the list
of offers and discard offers which the taker's user deems are too
expensive. One of the remaining offers is randomly chosen with weighting
determined by the fidelity bond value. Once an offer is chosen it is
removed from the list, and another offer is again randomly chosen, this
is repeated until the taker has chosen the desired number of
fidelity-bonded maker's offers.

Some people run makers not for profit but for their own privacy.
Therefore not all makers should be required to have bonds, because such
privacy-makers are useful to include in coinjoins too. We could have
taker allow say, an eighth (12.5%), of their coinjoin peers to be makers
without bonds. They can be chosen randomly from the orderbook without
any weighting based on fidelity bond values. Of course these are easy to
fake by an adversary so they dont contribute much to sybil resistance.

### Cost of sybil attacks

See the other document (Cost of sybil attacks) for discussion and
calculations on the sybil resistance given by the above maker-choosing
algorithm.

It can be calculated that the fidelity bond system dramatically
increases the cost of a sybil attack. With real-world data and realistic
assumptions we can calculate that a sybil attacker would need to lock up
30,000-80,000 bitcoins for 6 months, or send 45-120 bitcoins to burner
addresses to have a good chance of attacking the system by being all the
counterparties in everyone's coinjoin.

## Effect of fidelity bonds on CoinJoin fees

Someone might ask "why would anyone lock up coins for months or more,
let alone burn coins forever, just to run a maker bot". The only way
this would even happen is if makers can generate a higher income that
justifies the fidelity bond sacrifice. That higher income can only come
from taker's coinjoin fees (or possibly coinswap fees one day). We can
expect that makers with higher valued fidelity bonds will demand higher
coinjoin fees. So a big question is whether takers will accept paying
higher coinjoin fees. I think they will, because right now coinjoin fees
are only 10-1000 satoshi, and a far biggest cost of coinjoins is the
miner fee not the coinjoin fee. I'm pretty sure takers will recognize
that they get what they pay for, and that additional privacy is well
worth the cost. Any other takers reading this should definitely let me
know what they think.

## Technical ideas

JoinMarket's wallet could also create time-locked addresses. Locktimes
should be fixed to be midnight on the first day of each month, then each
public key corresponds to 12 addresses per year (1200 addresses per
century) which is very practical to all be monitored as watch-only
addresses. These wallets can be created offline and could safely hold
time-locked bitcoins.

The timelocked addresses public key can be used to sign an IRC nickname
proving that the nickname is the real owner of the TXO. OP_RETURN
outputs used for burning coins can include a pubkey hash used for the
same thing.

We don't want the cold storage keypairs to be held online. We can design
the system that the time-locked address keypair is held offline but it
signs another key pair which is held online. Every time the IRC bot
connects it can use this intermediate keypair to sign the IRC nickname
proving ownership. The signature from the time-locked address to the
intermediate keypair can be made to have an expiry date (for example 6
months). This all means that the time-locked bitcoins can be held
offline but still be used to prove ownership of an IRC nickname.

The existance of the UTXO of a time-locked coin can be proved by
revealing the TXID and vout, which full nodes can use to query the UTXO
set to check that the coin exists. SPV clients would need a merkle proof
as well. Burned coins and spent time-locked coins could have their
existence proved by sharing the transaction which created them along
with a block height and transaction position for an unpruned node, or a
merkle proof for a pruned node or SPV client. Note that from the point
of view of a pruned node, a merkle proof is a fully-verified proof of
existance of a transaction. It is not a proof with just SPV-security.

## Links / References
[1] https://github.com/JoinMarket-Org/joinmarket-clientserver
[2] https://github.com/JoinMarket-Org/joinmarket/issues/693
[3] https://en.bitcoin.it/wiki/Fidelity_bonds
[4] https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b
[5]
https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b#cost-of-sybil-attacks
[6] First ever mention of fidelity bonds I found. The idea is basically
invented by Peter Todd: https://bitcointalk.org/index.php?topic=134827.0
[7] Old idea for combining fidelity bonds with mixers:
https://bitcointalk.org/index.php?topic=172047.0
[8] Suggestion that is very close to the fidelity bonds idea. He talks
about requiring a deposit from makers, but nobody is able to come up
with a way to make such a deposit decentralized and trustless:
https://www.reddit.com/r/Bitcoin/comments/2zc5tc/joinmarket_increase_the_privacy_of_bitcoin_and/ctk37hn/?context=1

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

[Tamas Blummer]

[-- Attachment #1: Type: text/plain, Size: 14688 bytes --]

Hi Chris,

yes, fidelity bonds can impose cost to make sybill attacks more expensive therefore less likely.
I prefer the flavor with CHECKSEQUENCEVERIFY which imposes opportunity cost, just as effective
as burning, but is sustainable.

Imposing opportunity costs however requires larger time locked amounts than burning and the
user might not have sufficient funds to do so. This is however not a restriction but an opportunity
that can give rise to an additional market of locking UTXOs in exchange of a payment.

This would give rise to a transparent interest rate market for Bitcoin an additional huge benefit.

Regards,

Tamas Blummer

> On Jul 25, 2019, at 13:47, Chris Belcher via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> 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 the sacrificed amount (as well as other factors),
> knowing that a sybil attacker would also have to sacrifice a certain
> amount of coins in order to unmix the taker's coinjoins. The sacrifice
> would be an objective measurement that can't be faked and which can be
> verified by anybody (just like, for example PoW mining)
> 
> Note that a long-term holder (or hodler) of bitcoins can buy time-locked
> fidelity bonds essentially for free, assuming they never intended to
> transact with their coins much anyway. 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.
> 
> ### Fidelity bonds in cold storage
> 
> The private keys of fidelity bonds can be kept offline. Signatures
> potentially only need to be made when the timelock expires (every 6
> months for example), or only once in the case of OP_RETURN burned coins.
> This allows JoinMarket's sybil resistance to increase without the hot
> wallet risk.
> 
> Burned coin signatures should still have a lifetime, in case the private
> key associated with the IRC nick (which is online) is stolen, so that
> the thief of that privkey can't impersonate the maker indefinitely. The
> signature linking the burned coins and IRC nick could expire after
> perhaps 6 months.
> 
> ### Anonymity
> 
> Under this scheme makers would need to publish the transactions of their
> fidelity bonds to the entire world. Those transactions could be subject
> to blockchain analysis. So before makers do this they should make sure
> their coins are anonymous (possibly by mixing with JoinMarket). Also if
> they ever want to use their coins for something else apart from fidelity
> bonds they should mix them.
> 
> ### Value of a fidelity bond
> 
> See the other document (Financial mathematics of joinmarket fidelity
> bonds)[4] for a formula expressing the value of a fidelity bond.
> 
> The value of a fidelity bond made by sending V bitcoins to a burner
> address is:
> 
>    V^2
> 
> The amount of bitcoins is squared to get the fidelity bond value. This
> has the effect that economic-rational makers have a strong incentive to
> lump up all their coin sacrifices together into one maker bot, not to
> split it up over several bots.
> 
> The value of a fidelity bond made by locking up V bitcoins in a
> time-locked address for time period T is:
> 
>    V^2 (exp(rT) - 1)^2
> 
> To get an idea of the numbers, if we burn 2 btc then the value of the
> fidelity bond is 4 BTC^2. If we lock up 100 BTC for one year, and have a
> bitcoin interest rate r = 0.001 (0.1%) per year, then the value of that
> fidelity bond is 0.01 BTC^2 which is the same as burning 0.1 BTC. That
> is a relatively small valued bond. It can be increased by locking up
> more bitcoins for longer (up to and including permanant locking via a
> burner transaction).
> 
> ## Taker algorithm for choosing makers
> 
> I suggest the following taker peer choosing algorithm: obtain the list
> of offers and discard offers which the taker's user deems are too
> expensive. One of the remaining offers is randomly chosen with weighting
> determined by the fidelity bond value. Once an offer is chosen it is
> removed from the list, and another offer is again randomly chosen, this
> is repeated until the taker has chosen the desired number of
> fidelity-bonded maker's offers.
> 
> Some people run makers not for profit but for their own privacy.
> Therefore not all makers should be required to have bonds, because such
> privacy-makers are useful to include in coinjoins too. We could have
> taker allow say, an eighth (12.5%), of their coinjoin peers to be makers
> without bonds. They can be chosen randomly from the orderbook without
> any weighting based on fidelity bond values. Of course these are easy to
> fake by an adversary so they dont contribute much to sybil resistance.
> 
> ### Cost of sybil attacks
> 
> See the other document (Cost of sybil attacks) for discussion and
> calculations on the sybil resistance given by the above maker-choosing
> algorithm.
> 
> It can be calculated that the fidelity bond system dramatically
> increases the cost of a sybil attack. With real-world data and realistic
> assumptions we can calculate that a sybil attacker would need to lock up
> 30,000-80,000 bitcoins for 6 months, or send 45-120 bitcoins to burner
> addresses to have a good chance of attacking the system by being all the
> counterparties in everyone's coinjoin.
> 
> ## Effect of fidelity bonds on CoinJoin fees
> 
> Someone might ask "why would anyone lock up coins for months or more,
> let alone burn coins forever, just to run a maker bot". The only way
> this would even happen is if makers can generate a higher income that
> justifies the fidelity bond sacrifice. That higher income can only come
> from taker's coinjoin fees (or possibly coinswap fees one day). We can
> expect that makers with higher valued fidelity bonds will demand higher
> coinjoin fees. So a big question is whether takers will accept paying
> higher coinjoin fees. I think they will, because right now coinjoin fees
> are only 10-1000 satoshi, and a far biggest cost of coinjoins is the
> miner fee not the coinjoin fee. I'm pretty sure takers will recognize
> that they get what they pay for, and that additional privacy is well
> worth the cost. Any other takers reading this should definitely let me
> know what they think.
> 
> ## Technical ideas
> 
> JoinMarket's wallet could also create time-locked addresses. Locktimes
> should be fixed to be midnight on the first day of each month, then each
> public key corresponds to 12 addresses per year (1200 addresses per
> century) which is very practical to all be monitored as watch-only
> addresses. These wallets can be created offline and could safely hold
> time-locked bitcoins.
> 
> The timelocked addresses public key can be used to sign an IRC nickname
> proving that the nickname is the real owner of the TXO. OP_RETURN
> outputs used for burning coins can include a pubkey hash used for the
> same thing.
> 
> We don't want the cold storage keypairs to be held online. We can design
> the system that the time-locked address keypair is held offline but it
> signs another key pair which is held online. Every time the IRC bot
> connects it can use this intermediate keypair to sign the IRC nickname
> proving ownership. The signature from the time-locked address to the
> intermediate keypair can be made to have an expiry date (for example 6
> months). This all means that the time-locked bitcoins can be held
> offline but still be used to prove ownership of an IRC nickname.
> 
> The existance of the UTXO of a time-locked coin can be proved by
> revealing the TXID and vout, which full nodes can use to query the UTXO
> set to check that the coin exists. SPV clients would need a merkle proof
> as well. Burned coins and spent time-locked coins could have their
> existence proved by sharing the transaction which created them along
> with a block height and transaction position for an unpruned node, or a
> merkle proof for a pruned node or SPV client. Note that from the point
> of view of a pruned node, a merkle proof is a fully-verified proof of
> existance of a transaction. It is not a proof with just SPV-security.
> 
> ## Links / References
> [1] https://github.com/JoinMarket-Org/joinmarket-clientserver
> [2] https://github.com/JoinMarket-Org/joinmarket/issues/693
> [3] https://en.bitcoin.it/wiki/Fidelity_bonds
> [4] https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b
> [5]
> https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b#cost-of-sybil-attacks
> [6] First ever mention of fidelity bonds I found. The idea is basically
> invented by Peter Todd: https://bitcointalk.org/index.php?topic=134827.0
> [7] Old idea for combining fidelity bonds with mixers:
> https://bitcointalk.org/index.php?topic=172047.0
> [8] Suggestion that is very close to the fidelity bonds idea. He talks
> about requiring a deposit from makers, but nobody is able to come up
> with a way to make such a deposit decentralized and trustless:
> https://www.reddit.com/r/Bitcoin/comments/2zc5tc/joinmarket_increase_the_privacy_of_bitcoin_and/ctk37hn/?context=1
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

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

[Dmitry Petukhov]

[-- Attachment #1: Type: text/plain, Size: 1400 bytes --]

В Fri, 26 Jul 2019 10:10:15 +0200
Tamas Blummer via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
wrote:

> Imposing opportunity costs however requires larger time locked
> amounts than burning and the user might not have sufficient funds to
> do so. This is however not a restriction but an opportunity that can
> give rise to an additional market of locking UTXOs in exchange of a
> payment.
> 
> This would give rise to a transparent interest rate market for
> Bitcoin an additional huge benefit.

Wouldn't that 'locked utxo rent' market just drive the cost of attack
down to manageable levels for the attacker ?

The owner of the locked utxo can derive potential profit from it by
being a maker, and then the profit will be reduced by operational
expenses of running a maker operation.

The owner of utxo can just 'outsource' that task to someone, and pay
some fee for the convenience.

In effect, the owner would be renting out that utxo for the price of

<maker_profit> - <operational_expenses> - <convenience_fee>

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.

[-- Attachment #2: Цифровая подпись OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Chris Belcher]

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

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

[Dmitry Petukhov]

В Tue, 30 Jul 2019 22:39:14 +0100
Chris Belcher via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
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.

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

[Chris Belcher]

On 31/07/2019 16:50, Dmitry Petukhov wrote:
> В Tue, 30 Jul 2019 22:39:14 +0100
> Chris Belcher via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
> 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.

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

[Chris Belcher]

On 02/08/2019 10:50, Dmitry Petukhov wrote:
> В Fri, 2 Aug 2019 10:21:57 +0100
> Chris Belcher <belcher@riseup.net> 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

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

[Leo Wandersleb]

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.

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

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.

How about turning this upside down and shift the incentives from being taker to
being maker by introducing a mandatory fee? If each join costs 1% per maker,
people would initially gasp and reject to update to that version but those who
do, will do to become makers, increasing the maker count massively and
eventually most people in frequent need of joining will also become makers to
offset the costs of being takers.

With these changed rules again the sibyl attackers would still have their
competitive edge and would flood the market with even more cheap offers but now
everybody would have an incentive to do the same and as makers have to have the
UTXOs, it's not free to sibyl attack already.

LW

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

[Chris Belcher]

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.

> How about turning this upside down and shift the incentives from being taker to
> being maker by introducing a mandatory fee? If each join costs 1% per maker,
> people would initially gasp and reject to update to that version but those who
> do, will do to become makers, increasing the maker count massively and
> eventually most people in frequent need of joining will also become makers to
> offset the costs of being takers.
> 
> With these changed rules again the sibyl attackers would still have their
> competitive edge and would flood the market with even more cheap offers but now
> everybody would have an incentive to do the same and as makers have to have the
> UTXOs, it's not free to sibyl attack already.
> 

Apart from the inability of developers to enforce any kind of price, I
don't think this scheme would fix the sybil attack problem, because a
sybil attacker still gets a higher gain (deanonymization + fees)
compared to honest makers (who earn just fees)

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

[Leo Wandersleb]

On 8/6/19 10:27 PM, Chris Belcher via bitcoin-dev wrote:
> 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.

To show how this argument is wrong, think about the market being split between
100 makers, each making 1% of the fees. By your argument, by colluding, they
could make far more than 100% of the fees.

Every cartel of makers pooling their bonds beating the odds can't be the goal.

And again, bonds are just a cost of business. If a $10/month in bonds (paid to a
guy to sign with his UTXOs or interest for BTCs lent or ...) leaves me with zero
fees, a $100/month with $1k in fees and $10k/month with $40k in fees, then there
might be a $1000/month barrier to entry for this market but there are enough
people with $10k available to enter the market and drive the fees (earned per
maker) down such that the barrier to entry increases even further. In the end,
only the holders of the 20 biggest bonds will get meaningful business and the
rest will lose their investment or just not bother being makers. And the sibyl
attackers again are the ones that put up the necessary funds with most ease of
them all.

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

[ZmnSCPxj]

Good morning Chris,


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

Would it not be possible the below?

* I rent some funds from Dmitry.
  I agree to pay him 0.5 BTC for this service of putting up 50BTC from Dmitry UTXO.
* I also own 50BTC myself in a separate UTXO.
* We create a funding transaction paying out to a Schnorr MuSig output that is 2-of-2 between us.
  This spends Dmitry UTXO 50 BTC and my UTXO 50BTC.
  We only create this yet and do not sign.
* We create a backout transaction, probably with `nLockTime`, paying out 50.5BTC to Dmitry and 49.5BTC to me.
  This spends the funding transaction.
  We sign this using MuSig.
* After we exchange the signatures of the backout transaction, we exchange signatures for the funding transaction.
* Now we have a common 100BTC UTXO (indistinguishable from other Schnorr single-sig UTXOs) that can be used as fidelity bond for me.
  This is the output of the funding transaction.

The above can be scaled up so I can rent arbitrary amounts of coin from many different people, who are assured of getting their funds back, in exchange for a fidelity bond / advertisement, and thus greatly destroying the properties of the V^2 tweak.

(The ability to have shared ownership of UTXOs is a powerful feature of Bitcoin, and backs its ability to scale, as witnessed with Lightning Network and channel factories.)

Regards,
ZmnSCPxj

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

[Dmitry Petukhov]

В Mon, 5 Aug 2019 20:04:26 +0100
Chris Belcher <belcher@riseup.net> 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.

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

[Dmitry Petukhov]

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 <dp@simplexum.com> wrote:

> В Mon, 5 Aug 2019 20:04:26 +0100
> Chris Belcher <belcher@riseup.net> 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.

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

[ZmnSCPxj]

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

>
> [1]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017217.html
>
> В Wed, 7 Aug 2019 01:55:41 +0500
> Dmitry Petukhov dp@simplexum.com wrote:
>
> > В Mon, 5 Aug 2019 20:04:26 +0100
> > Chris Belcher belcher@riseup.net 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

[Chris Belcher]

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

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

[ZmnSCPxj]

Good morning Chris,

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

At the cost of *greatly* strengthening aggregation.

Suppose there is currently many makers, all with roughly-equal bonds.
Suppose I were to approach two of these makers, and offer to aggregate their bonds.
The combined bond would, because of the V^2 term, have 4 times the weight of the other makers.
Thus, approximately I can earn a little below 4 times what one other maker does.
I offer 1.5x what one maker does to both of those makers and keep a little below 0.5x to myself.
So:

1.  I earn without putting any of my money into bonds.
    I just need starting capital to pre-pay for the rents.
2.  I get to learn a little below 4x more CoinJoins than other makers.
    This increases my earnings further since I can sell this privacy information, and I also get an advantage compared to other non-aggregating spies.

It seems to me not to fix the root issue, i.e. makers who make for the purpose of gathering privacy information, even if it might fix sybil attackers.

Regards,
ZmnSCPxj

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

[Chris Belcher]

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 <dp@simplexum.com> wrote:
> 
>> В Mon, 5 Aug 2019 20:04:26 +0100
>> Chris Belcher <belcher@riseup.net> 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.
> 
> 

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

[ZmnSCPxj]

Good morning Dmitry,


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, August 7, 2019 6:05 PM, Chris Belcher via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

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

Possibly not so much?
The wallet need only sign two things:

1.  The fidelity bond itself.
2.  The backout transaction.

Both can be done in a single session, then the private key involved can be erased permanently from memory.
Only the signature for the backout needs to be stored, and this can be safely stored without encryption by publishing to any cloud service --- others getting a copy of the signature does not let them change the signature to authorize a different transaction.
It would be enough to write the signing code in C and use special OS calls (which most languages higher than C do not expose) to allocate memory that will never be put in swap.
Then generate the private key using that memory, then clear it after usage before deallocating to the OS.
I believe `libsecp256k1` makes this easy.

Unless part of the bond process requires that the taker do a challenge "sign this random nonce for me", but of note is that it would have to impose this on all makers.
But if so, consider again this:

1.  There exists two non-spying makers with nearly-equal bond values.
2.  These makers need to keep their bond private keys in hot storage.
3.  I approach both makers and offer to aggregate their bond values, forming a new bond with 4x the weight of their individual bonds, and split up the increased earnings between us.
    This can be made noncustodial by use of smart contracts on Bitcoin.
4.  It is no different from the point of view of both makers: they still need to keep their bond private keys in hot storage.
    But this way earns them more money than operating as non-spying makers.
5.  I earn not only the fees for JoinMarket, I also earn additional fees for spying on CoinJoins.

It still seems to me that adding the V^2 tweak weakens the bond system, not strengthens it.

Regards,
ZmnSCPxj

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

[Dmitry Petukhov]

В Wed, 7 Aug 2019 11:05:41 +0100
Chris Belcher <belcher@riseup.net> wrote:

> 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 second scheme ("all locked TXO may be required to be spendable
by *any* key that controls any TXO in the 'bond TXO package'") is in
almost all regards the same as simple "require TXO to be consolidated",
and looks like it is not in any way better than simple consolidation.

The first scheme - 'allow revocation of the whole bond by the key
controlling even a single TXO in a bond' - might be more promising.

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

In the second scheme, to revoke/spoil the bond, the entity that
controls one TXO participating in this bond needs to simply prove that
it somehow controls/have the ability to spend that TXO.

In shared ownership rent scheme that ZmnSCPxj described in [1],
the 'TXO rentier' has a signed timelocked 'backout' transaction that
spends the locked TXO, and assigns the reward to rentier.

If we say that any transaction that spends any TXO in the bond
(ignoring the timelock), invalidates the bond when presented to
takers, then TXO rentier can revoke the bond by simply
publishing this transaction (not to the blockchain, but by some other
means so that takers can receive it).

The transaction validity can be verified, with the relaxed rules that
ignores the timelock. After it is verified, takers mark the whole
bond as revoked and will not consider it when chosing makers.

One inconvenience here is that takers need to store the
data about revoked bonds. But it seems to me that there's no need
for that information to be synchronized between the participants
instantly. It is enougth for takers to get the revoked-set eventually.

The rentier are still incentivized to not spoil the bond, to receive
the profit. Their funds are locked anyway.

But if the goal of the 'rentier' is to attack the attacker, the
opportunity cost of these locked funds is the cost of the attack.

If the renter rents TXOs from several entities to include in one bond,
revocation by one rentier spoils whole bond, and the total loss for all
participants is bigger than the oportunity cost of locked funds of a
single rentier that made the revocation. 

The possibility of such revocation increases risk for the renter and
would-be co-rentiers, and is likely limit the possible scale of such
TXO-renting operation.
 
[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017217.html

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

[ZmnSCPxj]

Good morning Dmitry,

> The first scheme - 'allow revocation of the whole bond by the key
> controlling even a single TXO in a bond' - might be more promising.

Is it?
I imagine any key can secretly be a MuSig or aggregated ECDSA key, with the aggregator being a signatory.

>
> > 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.
>
> In the second scheme, to revoke/spoil the bond, the entity that
> controls one TXO participating in this bond needs to simply prove that
> it somehow controls/have the ability to spend that TXO.
>
> In shared ownership rent scheme that ZmnSCPxj described in [1],
> the 'TXO rentier' has a signed timelocked 'backout' transaction that
> spends the locked TXO, and assigns the reward to rentier.
>
> If we say that any transaction that spends any TXO in the bond
> (ignoring the timelock), invalidates the bond when presented to
> takers, then TXO rentier can revoke the bond by simply
> publishing this transaction (not to the blockchain, but by some other
> means so that takers can receive it).
>
> The transaction validity can be verified, with the relaxed rules that
> ignores the timelock. After it is verified, takers mark the whole
> bond as revoked and will not consider it when chosing makers.
>
> One inconvenience here is that takers need to store the
> data about revoked bonds. But it seems to me that there's no need
> for that information to be synchronized between the participants
> instantly. It is enougth for takers to get the revoked-set eventually.
>
> The rentier are still incentivized to not spoil the bond, to receive
> the profit. Their funds are locked anyway.
>
> But if the goal of the 'rentier' is to attack the attacker, the
> opportunity cost of these locked funds is the cost of the attack.
>
> If the renter rents TXOs from several entities to include in one bond,
> revocation by one rentier spoils whole bond, and the total loss for all
> participants is bigger than the oportunity cost of locked funds of a
> single rentier that made the revocation.
>
> The possibility of such revocation increases risk for the renter and
> would-be co-rentiers, and is likely limit the possible scale of such
> TXO-renting operation.

This is quite a clever solution.

Let me then attempt to break it.

It is possible to encrypt data in such a way that it requires sequential operations in order to decrypt.
https://www.gwern.net/Self-decrypting-files

This basically allows us to encrypt some data in such a way that its decryption is timelocked, by requiring a large number of sequential operations to decrypt.

It also seems to me (I am not a cryptographer) that it may be possible to present a ZKP that an encrypted text, encrypted using the above timelock decryption, is a signature of a particular message with a particular public key.

Thus, we can change the ritual to this:

1.  I contact two lessors to aggregate their coins into a larger UTXO and thus break V^2.
2.  We create a funding transaction that pays to a locked bond address, with a pubkey equal to a MuSig among us.
    This spends the TXOs they want to lease out, as well as some of my funds to be used for paying for rent.
    We do not sign this yet.
3.  We create a backout transaction that returns the bond to both lessors, plus their rent.
    We partly perform the MuSig ritual to sign this transaction, with me as the last step.
4.  Instead of providing the completed signature to the lessors, I encrypt it using the above timelocked encryption.
    I provide this encryption and a zero-knowledge proof that I have actually completed the signature ritual correctly and that the timelocked-encrypted text has the signature as plaintext.
5.  The lessors now know they can acquire the signature by simply grinding the timelocked encryption.
    This allows them to recover their money by the appointed time.
6.  We then exchange signatures for the funding transaction and broadcast and confirm it.

Now, the lessors cannot provide a valid timelocked transaction, as they do *not* yet have a complete signature; thus they cannot snitch about my aggregation of their funds.
At the same time, they know that the timelocked encryption allows them to eventually get a complete signature and recover their funds.
I can defray this cost of processing by increasing my rent slightly.

Now of course we can just go one step further and also allow bonds to be snitched by presenting the timelocked-encrypted text and the ZKP that it contains the signature for a timelocked transactions.
But it seems to me that there is more than one way to skin this particular cat, thus unless all ways to create provable timelocked encryptions are enumerable, it would be possible to get around.

(though of course it is dependent on a ZKP being possible for a timelocked encryption)

Finally, aggregation is still possible to insure by off-blockchain agreements, possibly with legal consequences, and thus entities like exchanges might still be able to aggregate funds and acquire an undeservedly large weight in the fidelity bond system.

Regards,
ZmnSCPxj

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

[ZmnSCPxj]

Good morning Dmitry, and list,

> > > 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.
> >
> > In the second scheme, to revoke/spoil the bond, the entity that
> > controls one TXO participating in this bond needs to simply prove that
> > it somehow controls/have the ability to spend that TXO.
> > In shared ownership rent scheme that ZmnSCPxj described in [1],
> > the 'TXO rentier' has a signed timelocked 'backout' transaction that
> > spends the locked TXO, and assigns the reward to rentier.
> > If we say that any transaction that spends any TXO in the bond
> > (ignoring the timelock), invalidates the bond when presented to
> > takers, then TXO rentier can revoke the bond by simply
> > publishing this transaction (not to the blockchain, but by some other
> > means so that takers can receive it).
> > The transaction validity can be verified, with the relaxed rules that
> > ignores the timelock. After it is verified, takers mark the whole
> > bond as revoked and will not consider it when chosing makers.
> > One inconvenience here is that takers need to store the
> > data about revoked bonds. But it seems to me that there's no need
> > for that information to be synchronized between the participants
> > instantly. It is enougth for takers to get the revoked-set eventually.
> > The rentier are still incentivized to not spoil the bond, to receive
> > the profit. Their funds are locked anyway.
> > But if the goal of the 'rentier' is to attack the attacker, the
> > opportunity cost of these locked funds is the cost of the attack.
> > If the renter rents TXOs from several entities to include in one bond,
> > revocation by one rentier spoils whole bond, and the total loss for all
> > participants is bigger than the oportunity cost of locked funds of a
> > single rentier that made the revocation.
> > The possibility of such revocation increases risk for the renter and
> > would-be co-rentiers, and is likely limit the possible scale of such
> > TXO-renting operation.
>
> This is quite a clever solution.
>
> Let me then attempt to break it.
>
> It is possible to encrypt data in such a way that it requires sequential operations in order to decrypt.
> https://www.gwern.net/Self-decrypting-files

I apologize, I was being daft.
There is a simpler way to break this, involving such Lightning Network tropes as revocation and punishment schemes.
Truly, Lightning Network is a great great thing.

First, we should always consider, that due to the V^2, consolidated bonds are always higher weight than unconsolidated bonds.
Thus, even without considering motives to spy on CoinJoins, the existence of the V^2 tweak implies that there will be fewer larger makers and thus easier to take over the JoinMarket system.

So, let us focus on the backout transaction.
Under a consolidated bond, this requires an n-of-n.

Now, suppose we want to identify the snitch who reports our consolidation scheme to the takers.
This can be done easily by performing n MuSig n-of-n rituals, with each ritual using different `r` nonces.
We arrange this by having each of the n consolidators be the last signers in the second round of the MuSig, and have each signer keep their own unique version of the signature for the backout, with their own unique `r` nonce.

Each participant will want to keep its own version of the signature private, because if it gives out this signature to another participant in the consolidated bond scheme, the other participant can frame them for snitching.

We can now identify the snitch, by recognizing which signature was used in the transaction that was reported to the takers.
But we have not yet identified how we can punish the snitch.

As it happens, MuSig allows Scriptless Script.
This means, it is possible for one participant in the MuSig to provide an adaptor signature.
This adaptor signature commits to a particular point.
When the MuSig is completed and the participant (who is the last signer in the second round of MuSig) reveals the completed signature, the scalar that generates the commited point can be computed by anyone who knows the adaptor signature.

This is our next step in our scheme to identify and punish snitches.
In addition to putting up their funds in a consolidated bond, each of the participants in the consolidation scheme put up a fraction of the value into revocable bonds.

This revocable bond is a Taproot with a known-NUMS point as internal Taproot key, and the script alternatives below:

    <bond_time - 1> OP_CHECKLOCKTIMEVERIFY OP_DROP <participant_key> OP_CHECKSIG

and

    <MuSig(all participants *except* this participant)> OP_CHECKSIGVERIFY <participant_snitch_key> OP_CHECKSIG

A punishment transaction spends from the revocable bond via the second alternative above, and divides it equally among the *other* participants.
THis is signed using the MuSig above (where all participants except the owner of this revocable bond are part of).

Then, before starting the n rituals to sign the backoff transaction, the participants provide adaptor signatures to their own `participant_snitch_key`, such that if they publish the backoff transaction to the takers, any of their co-participants that masquerades as a taker can find out about this and derive the private key to the `participant_snitch_key`.

So:

1.  In case all the participants cooperate with the other consolidators, then just before the bond expires, each participant can recover their revocable bond via the first alternative shown above.
    Once the revocable bond is spent back to an address they solely control, the `participant_snitch_key` is worthless.
    Then any participant can publish onchain the backoff transaction without repercussion.
2.  In case a participant snitches and reveals a pre-signed backoff to the takers before the end of the bond period, they can only reveal their own version of the signature of the backoff transaction.
    In that case, their previously-shown adaptor signature can be used to reveal the private key behind their `participant_snitch_key`.
    Then any one of the other participants in the consolidation scheme can complete the punishment transaction.

We can even ensure that setup of the whole system is atomic, by unironically CoinJoining the creation of the consolidated JoinMarket V^2 fidelity bond, in the same transaction that creates the revocable bonds that can be used to ensure that snitches are punishable.

Now you might say, "well now the bond they can put into the JoinMarket fidelity bond is smaller because of the need to put a revocable bond".
And that is right.
It also shows that the V^2 tweak is broken.

Suppose there are two makers with 1.0 BTC each.
They decide to consolidate their bond in order to increase their consolidated weight in the JoinMarket fidelity bond system.
They decide to put up 0.25BTC each for the revocable bonds, and 0.75BTC each into the consolidated JoinMarket V^2 fidelity bond.
The total consolidated bond is 1.5BTC, which has a weight 2.25x the weight of one 1.0BTC bond, or 1.125x the weight of 2x 1.0BTC bonds.
Thus consolidation pressure still exists strongly (and I would think that losing as little as 5% of your total bondable funds would be enough to discourage snitches: this example is 25%).

The scheme would not be broken if there was no V^2 tweak, and would have worked perfectly to disable consolidation, if not for the V^2 tweak.

Regards,
ZmnSCPxj

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

[Dmitry Petukhov]

В Thu, 08 Aug 2019 09:35:24 +0000
ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> <MuSig(all participants *except* this participant)> OP_CHECKSIGVERIFY
> <participant_snitch_key> OP_CHECKSIG

This anti-snitch protection won't work if there are two snitches, which
is concievable in the case of a large-scale consolidated bonds (one
entity can pretend to be two independent entities with two different
TXO). The snitch co-conspirator will refuse to sign the punishment
transaction.

If you change the MuSig(all_except_snitch) to 1-of-n multisig
construction so that anyone other than the actual 'snitch' can
confiscate the snitch-bond, then there's possibility that that a
co-conspirator can get that bond before others - even before
the sntich transaction is distributed to takers.

It seems that to reasonably protect from more than one snitch with this
punishment scheme, you want to make a multitude of taproot leaves where
each leaf can be spent by cooperation of N entities, where N is the
size of expected non-snitch participant set.

> Finally, aggregation is still possible to insure by off-blockchain
> agreements, possibly with legal consequences, and thus entities like
> exchanges might still be able to aggregate funds and acquire an
> undeservedly large weight in the fidelity bond system.

This seems to me like the most immediate problem for the discussed
system.

Since the centralized exchanges or other custodial services already
control TXOs of their customers who sent their funds there, they can
use them to make extra profit with joinmarket, and create fidelity
bonds out of these TXO with (or without) consent of the customers, and
pay them (or not) the amount according to their UTXO, while getting the
consolidation benefit of V^2 for themselves. It is also more probable
that such centralized custodial services would be willing to
participate in a deanonymization efforts, so that they can explain
their participation in coinjoins to regulators.

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

[ZmnSCPxj]

Good morning Dmitry,


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, August 8, 2019 7:37 PM, Dmitry Petukhov <dp@simplexum.com> wrote:

> В Thu, 08 Aug 2019 09:35:24 +0000
> ZmnSCPxj ZmnSCPxj@protonmail.com wrote:
>
> > <MuSig(all participants except this participant)> OP_CHECKSIGVERIFY
> > <participant_snitch_key> OP_CHECKSIG
>
> This anti-snitch protection won't work if there are two snitches, which
> is concievable in the case of a large-scale consolidated bonds (one
> entity can pretend to be two independent entities with two different
> TXO). The snitch co-conspirator will refuse to sign the punishment
> transaction.
>
> If you change the MuSig(all_except_snitch) to 1-of-n multisig
> construction so that anyone other than the actual 'snitch' can
> confiscate the snitch-bond, then there's possibility that that a
> co-conspirator can get that bond before others - even before
> the sntich transaction is distributed to takers.

The correct way to do this, as with any offchain technique, is to have the punishment transactions signed by the MuSig-of-everyone-other-than-punishment-target before you even sign the funding transaction.
If consolidation is subsidized by paying rent out to the consolidators, then the lessee of the UTXOs adds its rent payment in the same transaction that atomically instantiates the fidelity bond and all revocable bonds as a single CoinJoined transaction.
If any participant refuses to sign the punishment transactions of their co-consolidators, then the lessee refuses to sign the funding transaction and nobody earns any rent and the lessee goes look for another set of UTXO owners (or just kicks out the participant who refuses to sign and lives with the smaller fidelity bond, no big deal).

Of course, anyone renting consolidated bonds can themselves be unironic victims of sybil attackers who split up their funds to smaller parts so that their liability when later snitching is reduced, possibly to a level that is comfortable to them.
The sybil attacker then pretends to be lessors of UTXOs.

>
> It seems that to reasonably protect from more than one snitch with this
> punishment scheme, you want to make a multitude of taproot leaves where
> each leaf can be spent by cooperation of N entities, where N is the
> size of expected non-snitch participant set.
>
> > Finally, aggregation is still possible to insure by off-blockchain
> > agreements, possibly with legal consequences, and thus entities like
> > exchanges might still be able to aggregate funds and acquire an
> > undeservedly large weight in the fidelity bond system.
>
> This seems to me like the most immediate problem for the discussed
> system.
>
> Since the centralized exchanges or other custodial services already
> control TXOs of their customers who sent their funds there, they can
> use them to make extra profit with joinmarket, and create fidelity
> bonds out of these TXO with (or without) consent of the customers, and
> pay them (or not) the amount according to their UTXO, while getting the
> consolidation benefit of V^2 for themselves. It is also more probable
> that such centralized custodial services would be willing to
> participate in a deanonymization efforts, so that they can explain
> their participation in coinjoins to regulators.

Yes, down with the V^2 superlinearity, it is too strongly centralizing.

Regards,
ZmnSCPxj

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

[Chris Belcher]

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.

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

[Dmitry Petukhov]

В Wed, 7 Aug 2019 20:10:17 +0500
Dmitry Petukhov via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
wrote:

> In shared ownership rent scheme that ZmnSCPxj described in [1],
> the 'TXO rentier' has a signed timelocked 'backout' transaction that
> spends the locked TXO, and assigns the reward to rentier.
> 
> If we say that any transaction that spends any TXO in the bond
> (ignoring the timelock), invalidates the bond when presented to
> takers, then TXO rentier can revoke the bond by simply
> publishing this transaction (not to the blockchain, but by some other
> means so that takers can receive it).
> 
> The transaction validity can be verified, with the relaxed rules that
> ignores the timelock. After it is verified, takers mark the whole
> bond as revoked and will not consider it when chosing makers.

The backout transaction might not be timelocked itself, but can depend
on another timelocked transaction (made specifically to avoid the
backout transaction be timelocked). That extra transaction will need to
be broadcast before the backout transaction.

To account for that possibility, takers would need to either use more
relaxed verification rules (do not check if the inputs of the 'snitch
transaction' exist), or would need to check the whole package of
dependent transactions in which the last one spends the bond. 

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

[David A. Harding]

On Thu, Jul 25, 2019 at 12:47:54PM +0100, Chris Belcher via bitcoin-dev wrote:
> 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.

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.

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

Any full node (archival or pruned) can verify coin age using the UTXO
set.[1]  Unlike script-based timelock (CLTV or CSV), there is no current
SPV-level secure way to prove to lite clients that an output is still
unspent, however such verification may be possible within each lite
client's own security model related to transaction withholding attacks:

- Electrum-style clients can poll their server to see if a particular
  UTXO is unspent.

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

> Note that a long-term holder (or hodler) of bitcoins can buy time-locked
> fidelity bonds essentially for free, assuming they never intended to
> transact with their coins much anyway.

This is the thing I most like about the proposal.  I suspect most
honest makers are likely to have only a small portion of their funds
under JoinMarket control, with the rest sitting idle in a cold wallet.
Giving makers a way to communicate that they fit that user template
would indeed seem to provide significant sybil resistance.

-Dave

[1] See, bitcoin-cli help gettxout

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

[Tamas Blummer]

[-- Attachment #1: Type: text/plain, Size: 3730 bytes --]

Hi David,

Aquiring coin age is hard not only for an attacker but for any user that
happened to move his funds lately.

Even if coin age is available, proofs of using it to fund a particular operation
are not sybill resistant. Only a centralized service would know for sure that
proof is only used once and such centralization would defeat the purpose.

In contrast time locking such that it is uniquely linked with the operation
is always possible as funds could also be rented to lock in a decentralized manner.

Regards,

Tamas Blummer

> On Jul 27, 2019, at 21:34, David A. Harding via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> On Thu, Jul 25, 2019 at 12:47:54PM +0100, Chris Belcher via bitcoin-dev wrote:
>> 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.
> 
> 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.
> 
> 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).
> 
> Any full node (archival or pruned) can verify coin age using the UTXO
> set.[1]  Unlike script-based timelock (CLTV or CSV), there is no current
> SPV-level secure way to prove to lite clients that an output is still
> unspent, however such verification may be possible within each lite
> client's own security model related to transaction withholding attacks:
> 
> - Electrum-style clients can poll their server to see if a particular
>  UTXO is unspent.
> 
> - 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.
> 
>> Note that a long-term holder (or hodler) of bitcoins can buy time-locked
>> fidelity bonds essentially for free, assuming they never intended to
>> transact with their coins much anyway.
> 
> This is the thing I most like about the proposal.  I suspect most
> honest makers are likely to have only a small portion of their funds
> under JoinMarket control, with the rest sitting idle in a cold wallet.
> Giving makers a way to communicate that they fit that user template
> would indeed seem to provide significant sybil resistance.
> 
> -Dave
> 
> [1] See, bitcoin-cli help gettxout
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

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

[Tamas Blummer]

[-- Attachment #1: Type: text/plain, Size: 3716 bytes --]

In summary I see three mechansims of making use costly:

1. burn
2. time locked funds, locker will incure opportunity cost
3. proven coin age, holder did incure opportunity cost

I dislike burn as usage of a service is infinite while coin supply is finite.

I prefer time locked funds over coin age as locked funds do not need proof of
unspentness, they can not be spent. Therefore time locked funds can be sufficiently
proven with SPV. The user of the service could post SPV proof with the request.

Regards,

Tamas Blummer

> On Jul 27, 2019, at 21:34, David A. Harding via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> On Thu, Jul 25, 2019 at 12:47:54PM +0100, Chris Belcher via bitcoin-dev wrote:
>> 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.
> 
> 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.
> 
> 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).
> 
> Any full node (archival or pruned) can verify coin age using the UTXO
> set.[1]  Unlike script-based timelock (CLTV or CSV), there is no current
> SPV-level secure way to prove to lite clients that an output is still
> unspent, however such verification may be possible within each lite
> client's own security model related to transaction withholding attacks:
> 
> - Electrum-style clients can poll their server to see if a particular
>  UTXO is unspent.
> 
> - 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.
> 
>> Note that a long-term holder (or hodler) of bitcoins can buy time-locked
>> fidelity bonds essentially for free, assuming they never intended to
>> transact with their coins much anyway.
> 
> This is the thing I most like about the proposal.  I suspect most
> honest makers are likely to have only a small portion of their funds
> under JoinMarket control, with the rest sitting idle in a cold wallet.
> Giving makers a way to communicate that they fit that user template
> would indeed seem to provide significant sybil resistance.
> 
> -Dave
> 
> [1] See, bitcoin-cli help gettxout
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

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

[Chris Belcher]

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.

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

[David A. Harding]

On Tue, Jul 30, 2019 at 10:27:17PM +0100, Chris Belcher wrote:
> 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.

Probably.  A stronger form of my argument would apply to single-wallet
(or wallet library) problems of the type we see with depressing
regularity, such as reused nonces, weak nonces, brainwallets, and weak
HD seeds.  In some cases, this leads directly to theft and loss---but in
others, the problem is detected by a friendly party and funds can be
moved to a secure address before the problem is publicly disclosed and
attackers try to exploit it themselves.

If funds are timelocked, there's a greater chance that the issue will
become publicly known and easily exploitable while the funds are
inaccessible.  Then, at the time the lock expires, it'll become a race
between attackers and the coin owner to see who can get a spending
transaction confirmed first.

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

Good point.  There's also the case that some Electrum-style indexers
don't index more than a certain number of outputs sent to the same
address.  E.g., I believe Electrs[1] stops indexing by default after 100
outputs to the same address.

[1] https://github.com/romanz/electrs

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

I don't think that works.  If Bob sends 100 BTC to bc1foo and then uses
that UTXO as his fidelity bond, Mallory can subsequently send some dust
to bc1foo to invalidate Bob's bond.

To use compact block filters in a way that prevents spamming, I think
we'd need a different filter type that allowed you to filter by
outpoint.

-Dave

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

[Adam Gibson]

[-- Attachment #1: Type: text/plain, Size: 16888 bytes --]

reposted due to wrong email address:

I'd just like to repeat something I said years ago but is undoubtedly lost
now:

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

I criticised this point from the Moser paper at the time, in particular
because it was the headline grabbing result and in my opinion was only half
the truth, at best:

The $32K figure came from the assumption that swamping the bottom of the
order book (in other words, making lots of bots offering prices lower than
all the other bots) would lead to taking most of the join volume.

At the time, this was true and false to some extent: it was true that the
default order choosing algorithm was exponentially weighted to lower fees.
But it was also true even then that Takers could simply manually choose any
counterparty bots they liked (-P).

Also at the time I complained that it was trivial to implement other order
choosing algorithms, in particular I advocated (for its simplicity) "choose
randomly under a user specified maximum fee", and indeed since the paper we
have implemented that algorithm and it's now the default.

Note that this algorithm is the crudest variant of what was loosely called
"quantization" in this discussion between belcher and gmaxwell on the topic
some years ago:

https://github.com/JoinMarket-Org/joinmarket/issues/14#issuecomment-143509788

To me the crucial point is that the Taker's price sensitivity should not be
too large, although of course it cannot be zero!

So independent of changes in the makeup of the users of Joinmarket, that
analysis from 2016 was in my opinion a bit skewed at the time, and
completely wrong today.

None of this is a critique of the fidelity bonds idea, since the Sybil
threat is real in any case (see issue 693 as mentioned), but price-based
Sybilling is less effective than it seems based on that.

I'll continue my thoughts on fidelity bonds, for what they're worth, in the
active thread:
https://github.com/JoinMarket-Org/joinmarket-clientserver/issues/371

(for those not in the know, Joinmarket-Org/joinmarket-clientserver is the
active repo, not Joinmarket-Org/joinmarket).

Adam Gibson / waxwing / AdamISZ

On Thu, Jul 25, 2019 at 3:18 PM Chris Belcher via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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 the sacrificed amount (as well as other factors),
> knowing that a sybil attacker would also have to sacrifice a certain
> amount of coins in order to unmix the taker's coinjoins. The sacrifice
> would be an objective measurement that can't be faked and which can be
> verified by anybody (just like, for example PoW mining)
>
> Note that a long-term holder (or hodler) of bitcoins can buy time-locked
> fidelity bonds essentially for free, assuming they never intended to
> transact with their coins much anyway. 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.
>
> ### Fidelity bonds in cold storage
>
> The private keys of fidelity bonds can be kept offline. Signatures
> potentially only need to be made when the timelock expires (every 6
> months for example), or only once in the case of OP_RETURN burned coins.
> This allows JoinMarket's sybil resistance to increase without the hot
> wallet risk.
>
> Burned coin signatures should still have a lifetime, in case the private
> key associated with the IRC nick (which is online) is stolen, so that
> the thief of that privkey can't impersonate the maker indefinitely. The
> signature linking the burned coins and IRC nick could expire after
> perhaps 6 months.
>
> ### Anonymity
>
> Under this scheme makers would need to publish the transactions of their
> fidelity bonds to the entire world. Those transactions could be subject
> to blockchain analysis. So before makers do this they should make sure
> their coins are anonymous (possibly by mixing with JoinMarket). Also if
> they ever want to use their coins for something else apart from fidelity
> bonds they should mix them.
>
> ### Value of a fidelity bond
>
> See the other document (Financial mathematics of joinmarket fidelity
> bonds)[4] for a formula expressing the value of a fidelity bond.
>
> The value of a fidelity bond made by sending V bitcoins to a burner
> address is:
>
>     V^2
>
> The amount of bitcoins is squared to get the fidelity bond value. This
> has the effect that economic-rational makers have a strong incentive to
> lump up all their coin sacrifices together into one maker bot, not to
> split it up over several bots.
>
> The value of a fidelity bond made by locking up V bitcoins in a
> time-locked address for time period T is:
>
>     V^2 (exp(rT) - 1)^2
>
> To get an idea of the numbers, if we burn 2 btc then the value of the
> fidelity bond is 4 BTC^2. If we lock up 100 BTC for one year, and have a
> bitcoin interest rate r = 0.001 (0.1%) per year, then the value of that
> fidelity bond is 0.01 BTC^2 which is the same as burning 0.1 BTC. That
> is a relatively small valued bond. It can be increased by locking up
> more bitcoins for longer (up to and including permanant locking via a
> burner transaction).
>
> ## Taker algorithm for choosing makers
>
> I suggest the following taker peer choosing algorithm: obtain the list
> of offers and discard offers which the taker's user deems are too
> expensive. One of the remaining offers is randomly chosen with weighting
> determined by the fidelity bond value. Once an offer is chosen it is
> removed from the list, and another offer is again randomly chosen, this
> is repeated until the taker has chosen the desired number of
> fidelity-bonded maker's offers.
>
> Some people run makers not for profit but for their own privacy.
> Therefore not all makers should be required to have bonds, because such
> privacy-makers are useful to include in coinjoins too. We could have
> taker allow say, an eighth (12.5%), of their coinjoin peers to be makers
> without bonds. They can be chosen randomly from the orderbook without
> any weighting based on fidelity bond values. Of course these are easy to
> fake by an adversary so they dont contribute much to sybil resistance.
>
> ### Cost of sybil attacks
>
> See the other document (Cost of sybil attacks) for discussion and
> calculations on the sybil resistance given by the above maker-choosing
> algorithm.
>
> It can be calculated that the fidelity bond system dramatically
> increases the cost of a sybil attack. With real-world data and realistic
> assumptions we can calculate that a sybil attacker would need to lock up
> 30,000-80,000 bitcoins for 6 months, or send 45-120 bitcoins to burner
> addresses to have a good chance of attacking the system by being all the
> counterparties in everyone's coinjoin.
>
> ## Effect of fidelity bonds on CoinJoin fees
>
> Someone might ask "why would anyone lock up coins for months or more,
> let alone burn coins forever, just to run a maker bot". The only way
> this would even happen is if makers can generate a higher income that
> justifies the fidelity bond sacrifice. That higher income can only come
> from taker's coinjoin fees (or possibly coinswap fees one day). We can
> expect that makers with higher valued fidelity bonds will demand higher
> coinjoin fees. So a big question is whether takers will accept paying
> higher coinjoin fees. I think they will, because right now coinjoin fees
> are only 10-1000 satoshi, and a far biggest cost of coinjoins is the
> miner fee not the coinjoin fee. I'm pretty sure takers will recognize
> that they get what they pay for, and that additional privacy is well
> worth the cost. Any other takers reading this should definitely let me
> know what they think.
>
> ## Technical ideas
>
> JoinMarket's wallet could also create time-locked addresses. Locktimes
> should be fixed to be midnight on the first day of each month, then each
> public key corresponds to 12 addresses per year (1200 addresses per
> century) which is very practical to all be monitored as watch-only
> addresses. These wallets can be created offline and could safely hold
> time-locked bitcoins.
>
> The timelocked addresses public key can be used to sign an IRC nickname
> proving that the nickname is the real owner of the TXO. OP_RETURN
> outputs used for burning coins can include a pubkey hash used for the
> same thing.
>
> We don't want the cold storage keypairs to be held online. We can design
> the system that the time-locked address keypair is held offline but it
> signs another key pair which is held online. Every time the IRC bot
> connects it can use this intermediate keypair to sign the IRC nickname
> proving ownership. The signature from the time-locked address to the
> intermediate keypair can be made to have an expiry date (for example 6
> months). This all means that the time-locked bitcoins can be held
> offline but still be used to prove ownership of an IRC nickname.
>
> The existance of the UTXO of a time-locked coin can be proved by
> revealing the TXID and vout, which full nodes can use to query the UTXO
> set to check that the coin exists. SPV clients would need a merkle proof
> as well. Burned coins and spent time-locked coins could have their
> existence proved by sharing the transaction which created them along
> with a block height and transaction position for an unpruned node, or a
> merkle proof for a pruned node or SPV client. Note that from the point
> of view of a pruned node, a merkle proof is a fully-verified proof of
> existance of a transaction. It is not a proof with just SPV-security.
>
> ## Links / References
> [1] https://github.com/JoinMarket-Org/joinmarket-clientserver
> [2] https://github.com/JoinMarket-Org/joinmarket/issues/693
> [3] https://en.bitcoin.it/wiki/Fidelity_bonds
> [4] https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b
> [5]
>
> https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b#cost-of-sybil-attacks
> [6] First ever mention of fidelity bonds I found. The idea is basically
> invented by Peter Todd: https://bitcointalk.org/index.php?topic=134827.0
> [7] Old idea for combining fidelity bonds with mixers:
> https://bitcointalk.org/index.php?topic=172047.0
> [8] Suggestion that is very close to the fidelity bonds idea. He talks
> about requiring a deposit from makers, but nobody is able to come up
> with a way to make such a deposit decentralized and trustless:
>
> https://www.reddit.com/r/Bitcoin/comments/2zc5tc/joinmarket_increase_the_privacy_of_bitcoin_and/ctk37hn/?context=1
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 19295 bytes --]