13/7/2019
4/4/2021 (edited fixing formula and adding two graphs)
7/5/2021 (added appendix 1)
To read the context see the main document Design for improving joinmarket's resistance to sybil attacks using fidelity bonds.
We want to come up with a mathematical formula which gives the value of a fidelity bond. We want this function to be in the best interests of takers who use it. We aim for them to get the best possible sybil resistance.
The value of a fidelity bond is related to the value sacrified in order to create it. We can be guided by existing principles from financial mathematics. In the rest of the document we call the function f.
The fidelity bond value should be proportional to the square of the coins sacrificed. In maths symbols, if V is the amount of coins then:
f proportional to V^2
The quadratic factor has the effect that economic-rational makers, who are only interested in making money and not spying on people, have a strong incentive to lump up all their coin sacrifices into one maker bot. In the 2019 status quo JoinMarket, some economic-rational makers have decided to run multiple maker bots in order to earn more fee income. The quadratic factor in the fidelity bond formula should also help fix that behaviour, as it's obviously bad for privacy.
The quadratic factor increases the cost required by sybil attackers to spy on users, because an attacker must split up their coin hoard over multiple bots, and splitting up their hoard into 10 bots (because takers choose 10 makers for example) means that the resulting fidelity bonds are worth 100 times less due to the quadratic function.
It should be possible to use multiple transaction outputs to prove a fidelity bond. This is useful in the case where a person sacrifices A amount of coins, decides that they make good money from it and want to add more so they sacrifice an extra B coins. Their value sacrificed should be calculated as (A + B)^2 not A^2 + B^2, as long as they prove that the transaction outputs A and B are both owned by the same entity.
The quadratic factor might have a negative effect where multiple people might choose to pool together their bitcoin hoard into one bot so that each can earn a higher fee income. This would be bad for privacy, but it also adds massive custodial risk where there was none without pooling, so it's probably unlikely to happen.
It is easy to value fidelity bonds made by burning coins to OP_RETURN outputs. The sacrifice is equal to the number of bitcoins burned (squared). Or:
f = V^2
A bitcoin now is worth more than a bitcoin next year. Money has a time value, which represents time preference and gives rise to the phenomenon of interest rates. Interest payments paid out at every small time interval are called continuously-compounded interest payments. Consider a completely-riskless bank account which pays interest on deposits. The value of such an account A after time t which uses continuous-compounding and has an interest rate of r is given by:
A = exp(rt)
By the principle of arbitrage (it doesnt matter for these purposes that such a bank account doesnt exist), the function f for a time-locked fidelity bond is related to the sacrified interest payments:
f = (V (exp(rT) - 1))^2
=> f = V^2 (exp(rT) - 1)^2
where T is the total locked time, the difference between the OP_CHECKLOCKTIMEVERIFY timeout and when the coin was confirmed. The -1 term is there because the bank account principle doesn't contribute to the sacrifice, only the interest payments do.
We should ask what happens when the timelock expires. Now the coin is free to be put in an interest-bearing account again, but the old sacrifice has still happened. By the arbitrage principle the possible interest payments must be taken away from the fidelity bond value until it reaches zero. The value of a bond after the timelock expiry is:
f = V^2 ( (exp(rT) - 1) - (exp(r(t-L)) - 1) )^2
=> f = V^2 ( exp(rT) - exp(r(t-L)) )^2
where t is the current time and L is the time or block height where the locktime of the coin expires, so (t-L) is the amount of time that the coin has been free. We can see that at t = T + L the bond becomes worthless because its initial sacrifice due to the timelock has been cancelled out by the time the coin has been free.
Combining the two effects gives us a function valuing the time-locked fidelity bond from its creation.
f = V^2 ( exp(rT) - 1 - MAX(1, exp(r*MIN(0, t-L) - 1)) )^2
The MAX and MIN functions are used to start the clock ticking only after the timelock expires, and to stop the value becoming negative.
A burner-output fidelity bond is exactly the same as a time-locked fidelity bond where the locktime is infinite. But if we take T -> infinity in our equation then f -> infinity too when really it should become f = V^2. So we use the MAX function again to clamp the maximum value.
f = V^2 ( MAX(0, MIN(1, exp(rT) - 1) - MIN(1, exp(r*MAX(0, t-L)) - 1)) )
That is the final function valuing a fidelity bond. It has the following properties we want:
- The value of a fidelity bond created from a currently time-locked coin is f = V^2 (exp(rT) - 1)^2
- After the timelock expires the value starts to fall, f = V^2 ( exp(rT) - exp(r(t-L)) )^2, until eventually becoming worthless
- If the timelock is infinite then that's equivalent to a burned coin, so the value is f = V^2
Note that an approxmiation can be used to make quick computation easier: exp(rT) - 1 =~= rT for small values of rT (which almost always is small). So for example if 20 btc is locked up for a year with r=0.2% then we can quickly calculate the bond value with (20btc * 0.002 * 1)^2 = (20 * 0.002)^2 = (0.04)^2 = 0.0016 btc^2
Takers can configure their own value for r, but in reality the overwhelming majority of users will leave the default unchanged. So we need to come up with a suitable value for r. It's not directly measurable as there's no riskless bonds in bitcoin. It may be approximately measurable by finding the rate of return for running JoinMarket makers or lightning relaying node (although these also include the hot wallet risk).
r represents the tradeoff between the future and the present. Consider what happens if r is set too low: Then takers will undervalue bonds made from longer-locked-up coins, compared to higher-amount-but-shorter duration locksup. And the makers who get chosen for coinjoins will be the ones who lock up higher values for shorter times. As an absurd extreme, if we choose r=0.0000001% per annum (one part per billion) then 100,000 BTC could be locked up for 1 year but it would be worth less than burning just 0.0001 BTC. Which I find absurd that burning such a small amount of coins is the same sacrifice as locking up such a huge amount of coins for a year.
Consider what happens if r is set too high: Then takers will overvalue the bonds made from longer-locked-up coins, compared to the higher-amounts-but-shorter duration locksup. And the makers who get chosen for coinjoins will be the ones who lock up smaller values for longer times. As an absurd extreme, if we choose r=2000% per annum then locking up coins for just 12 days is exactly the same value as burning those coins, which i find absurd because after 12 days the coins would be freely-available again if locked up but not if they were burned.
So I think we don't need an exact value for r, and we should just pick a value vaguely in the right region. A value of r = 0.1% implies that locking up coins for 693 years is the same sacrifice as burning them, which is not absurd. We could also choose say r = 0.35% which implies locking up coins for 200 years is the same sacrifice as burning them. I can't see any negative effects if the true value was actually off by a small factor, and was actually 0.5% or 0.02%. See below for the formula:
interest_rate = log(2) / lockup_years_until_equal_to_burn
We need to work out quantitatively how much sybil resistance is provided by this fidelity bond scheme.
Sybil resistance will depend on the algorithm used by takers when choosing makers with fidelity bonds. I suggest the following taker peer choosing algorithm: obtain the list of offers and discard offers which the taker deems are too expensive. One of the remaining offers is randomly chosen with weighting determined by the fidelity bond value of each offer. Once an offer is chosen it is removed from the list, and another offer is randomly chosen again, this is repeated until the taker has chosen the desired number of fidelity-bonded maker's offers.
To sybil attack such a system, the attacker needs to create a situation where only his own bots are chosen a high proportion of the time (say 95% of the time).
The taker peer choosing algorithm involves repeatedly choosing from a set without replacement. This can be analyzed with probability tree diagrams. Take the example case where there are three offers (A, B, C) which have fidelity bond values of (10, 5, 1) and the taker wants to choose two of them. This can be drawn with the following probability tree diagram and used to find the probability that each outcome happens. Each branch has an associated probability determined by the fidelity bond values. The first choice A has a probability of the weight of A divided by the total weight.
first second outcome probability
choice choice
B (A, B) 10/16 * 5/6 = 52%
/
(5/6)
/
---- A
/ \
/ (1/6)
/ \
/ C (A, C) 10/16 * 1/6 = 10%
(10/16)
/ A (B, A) 5/16 * 10/11 = 28%
/ /
/ (10/11)
/ /
----(5/16)--- B
\ \
\ (1/11)
\ \
\ C (B, C) 5/16 * 1/11 = 3%
(1/16)
\ A (C, A) 1/16 * 10/15 = 4%
\ /
\ (10/15)
\ /
---- C
\
(5/15)
\
B (C, B) 1/16 * 5/15 = 2%
Probability tree diagrams like this can be easily implemented in software and used to analyze the probability of a sybil attack succeeding and the cost of such an attack.
A sybil attacker's best (i.e. cheapest) strategy is to create exactly as many sybil bots as peers that the taker will choose. If the sybil attacker creates more bots then their attack will be much more costly because of the V^2 term in the fidelity bond value formula.
We analyze sybil attacks by considering the collection of honest makers (H) and their total fidelity bond value. If the probability tree events goes to a branch with honest makers H then the sybil attack has failed, because at least one non-sybil bot will be included in the coinjoin. For example, say a taker is choosing 2 coinjoin peers and that the honest makers together have fidelity bond values of 10 (equivalent to about 3.2 bitcoins sent to a burner address). Say the sybil attacker creates two bots each with fidelity bond values of 100 (equivalent to 20 btc burned in total). We can draw the following probability tree diagram:
first second outcome probability
choice choice
---- H (sybil attack failed)
/
/
/
/
(20/220)
/ H (sybil attack failed)
/ /
/ (20/120)
/ /
--(100/220)-- A
\ \
\ (100/120)
\ \
\ B (A, B) 100/220 * 100/120 = 38%
(100/220)
\ H (sybil attack failed)
\ /
\ (20/120)
\ /
---- B
\
(100/120)
\
A (B, A) 100/220 * 100/120 = 38%
Note that the sybil attack success probability is only 38% + 38% = 76%. So about a quarter of the time the attack failed even though the sybil attacker sacrificed more than 6 times the amount of bitcoins that all the honest makers together sacrificed. This is because even one honest maker being chosen as a peer is enough to introduce uncertainly into the coinjoin. The taker needs to get lucky just once with it's choice of peer, the sybil attacker needs to get lucky every time. This heavily tips the balance towards the defenders of privacy. If the sybil attacker were to put all their bitcoins into one fidelity bond, instead of spreading them across many, the V^2 term would mean that they could earn much more money than anyone else. Their income would come from acting honestly not spying, and in doing so they would contribute to the security of JoinMarket.
Code for analyzing such probability tree diagrams with a CPU can be found here. It can be used to calculate the cost to a sybil attacker for attacking an orderbook with a success rate of 95%.
Take the example where the makers in the orderbook are honest and have fidelity bonds which together have value 1. This is equivalent to sending 1 btc to a burner address. The table below shows what bond values would be needed by an adversary to sybil attack such an orderbook, expressed in amount of btc burned.
Cost to successfully sybil attack where 1 BTC is burned by honest makers
| Counterparties | Burned coin requirement |
|---|---|
| 2 | 10.73862623 BTC |
| 3 | 17.84256072 BTC |
| 4 | 25.38540809 BTC |
| 5 | 33.24015403 BTC |
| 6 | 41.33543042 BTC |
| 7 | 49.62572786 BTC |
| 8 | 58.07959724 BTC |
| 9 | 66.67405854 BTC |
| 10 | 75.39161602 BTC |
| 11 | 84.21852280 BTC |
| 12 | 93.14370438 BTC |
Note that the value parameter only has meaning relative to other fidelity bond values. So you could multiply every bond value number by any factor and the results would still be valid (but the bitcoin amount changes as the square root).
We can estimate what this corresponds to in practice by using real-life data from the June 2019 JoinMarket orderbook. The graph shows the maxsizes offered.
In our estimate we say that each of these makers locks up maxsize amount of bitcoins for 6 months to create fidelity bonds. From that we can work out the fidelity bond value needed by an adversary to sybil attack the system, expressed this time in bitcoins required to be locked up for 6 months. The table below shows the data.
Cost to successfully sybil attack based on real-world data of honest makers
| Counterparties | Burned coin requirement | 6 month locked coin amount requirement |
|---|---|---|
| 2 | 19.25192139 BTC | 12834.61425981 BTC |
| 3 | 31.98766483 BTC | 21325.10988525 BTC |
| 4 | 45.51027950 BTC | 30340.18633198 BTC |
| 5 | 59.59205757 BTC | 39728.03837678 BTC |
| 6 | 74.10505220 BTC | 49403.36813394 BTC |
| 7 | 88.96767533 BTC | 59311.78355316 BTC |
| 8 | 104.12354586 BTC | 69415.69723925 BTC |
| 9 | 119.53146581 BTC | 79687.64387005 BTC |
| 10 | 135.16006930 BTC | 90106.71286939 BTC |
| 11 | 150.98471128 BTC | 100656.47418517 BTC |
| 12 | 166.98553769 BTC | 111323.69179484 BTC |
Another calculation can be done assuming some makers in the orderbook are already sybil attackers. We calculate the probability of success of a sybil attack assuming the top X makers are actually sybils controlled by the same person. We again use the real-world orderbook data from June 2019. The table below shows the success probability for different numbers of taker-chosen counterparties.
| Counterparties | Success probability |
|---|---|
| 2 | 44% |
| 3 | 54% |
| 4 | 60% |
| 5 | 48% |
| 6 | 30% |
| 7 | 23% |
| 8 | 22% |
| 9 | 9.9% |
| 10 | 4.9% |
| 11 | 2.1% |
| 12 | 0.72% |
| 13 | 0.32% |
Of course its worth noting that the hypothetical sybil attacker would earn much more money if they lumped all their sacrificed coins into one maker, instead of spreading them across many. So economic-rational makers at the top of the offerbook are likely to all be different entities.
This success probability is for just one coinjoin. In the case of repeated coinjoins like in the tumbler script the probabilities are multiplied; for 5 repeated coinjoins at 20% odds each, the success probability is (0.20)^5 = 0.032%.
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 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. The fidelity bond formula has a quadratic term which provides a strong incentive for honest economic-rational makers to lump their sacrificed coins together with one maker, not split them up amongst many maker bots.
We can use the capital asset pricing model (CAPM) to work out how much fees have to go up by (even though CAPM is wrong but its the simpliest and best we have)
This section is not yet completed.
- Probability tree diagrams https://www.onlinemathlearning.com/probability-without-replacement.html
- Financial Calculus: An Introduction to Derivative Pricing by Rennie and Baxter
The calculations about sybil attacks from external enemies (i.e. suppose the orderbook is full of honest makers, how much would a attacker have to sacrifice in order to successfully sybil attack) appear to be linear in the honest_weight value. If the honest_weight is scaled by a constant factor then the fidelity bond weight required by sybil attackers is also scaled by the same factor. Therefore it makes sense to do all calculations for a unit honest weight (i.e. honest_weight = 1) and then multiply when needed to calculate the resistance to a real attack.
When doing these calculations on a CPU I noticed the result seemed to closely follow a log function. This allows us to derive the required sybil weight for larger numbers of counterparties beyond what is possible to calculate with a CPU (the calculation runtime goes as O(N!) so it rapidly becomes not practical).
Fidelity bonds are also discussed in this podcast episode https://stephanlivera.com/episode/167/