HenrikJannsen
commented
1 year ago Great thanks for the proposal and analysis! As both traders need to have the exact same distribution for the delayed payout transaction we would need to roll that change out with a activation blockheight sufficiently far in the future so that we can be sure to release and enforce the updated version.
Do you can think of a case where the iteration would run endlessly? I guess not (it reminded me on the fee estimation problem but that's different as the input selection can change with adjusted fees, thus in some cases would never stop the adjustment iteration). We have a min. amount for the outputs. This could maybe cause issues? Maybe we can limit iterations to a certain number and spend the remaining as miner fee in case the sum of all BM shares is 100% (so that the LBM cannot abuse it).
stejbac
pazza83
ghost
The present capping algorithm
The current algorithm for determining the percentage of trade fee and DPT revenue going to each Burning Man subjects their (decayed) burn shares to a cap, determined by their respective (decayed) issuance shares. Specifically, this cap is the minimum of 11% and the decayed issuance share times 10 (the boost factor), so a contributor with X% decayed issuance has a capped burn share of no more than 10 * X% if X is less than 1.1 and no more than 11% otherwise. The limit of 11% payout per contributor is intended to prevent him from profiting by carrying out a bunch of trades (say as the buyer) and driving then into arbitration to get the DPT payout shares, since this will be less than the security deposit he paid, which is at least 15% of the trade amount (>11% of the total escrow amount).
In the event that some of the contributors get their shares capped, the sum of all the capped and uncapped shares will be less than 100%, so in this case the present algorithm scales all the remaining (uncapped) shares up by a uniform amount, so that the total remains at 100% (effectively distributing burn share evenly from the capped contributors to the uncapped contributors). This creates the problem that some of the adjusted (scaled up) burn shares could now themselves exceed their respective caps.
To solve this problem, the present algorithm applies a second round of capping as needed, making sure that none of the adjusted shares exceed their respective caps. But now the sum of all the shares will be less than 100%, so in that (hopefully rare) case, the remainder is set to go to the Legacy Burning Man. Note that there is no further cap in that case, and the LBM could theoretically get any amount of the revenue/payouts up to 100%.
There are two problems with the capping algorithm as it stands: 1) It is not as mathematically elegant as it could be. In particular, the (multivariate) function from tuples of uncapped burn shares to tuples of capped burn shares is not continuous. That is, a tiny perturbation in the uncapped burn percentages can sometimes lead to a large perturbation in the final capped burn percentages. To see this, suppose that there are two contributors A and B at or close to their respective caps, while the other contributors are far below their respective caps. If we suppose A is well above his cap and B is just slightly above his, then A and B will be capped in the first round and everyone else's shares will be adjusted upwards by the factor,
If OTOH B is slightly below his cap, then A will be capped in the first round, B will be capped in the second round and everyone else's shares will be adjusted upwards by the smaller factor,
Thus there is a big jump downwards in the adjustments of everyone else's shares, with the remainder going to the LBM.
2) By burning a large amount of BSQ on other contributors' behalf, it is possible for a corrupt LBM to manipulate the burn shares to result in a final DPT payout percentage of far greater than 11% going to him, which would allow him to profitably steal money from the traders by sweeping the offer book and driving the resultant trades into arbitration. This attack is explained below.
A hypothetical attack by the Legacy Burning Man.
Any Bisq user can burn BSQ on behalf of any other contributor to increase their burn share, since the decayed burn amounts are nothing more than ordinary proofs of burn with the hash of the contributor name in the
OP_RETURNdata field. Under the present capping algorithm, this opens up an attack vector by the LBM to give himself a share greater than 11%. To do this, he can pick a tiny contributor T with a negligible amount of the decayed issuance share, as well as several largish contributors A, B, C,..., each with say at least 1.1% of the decayed issuance share, so that their caps are all large, say around the maximum of 11%. He then burns a large amount on behalf of each of the large contributors, to push up their burn shares to around double their respective caps, say around 22% each. Finally, the LBM burns a very large amount on behalf of the tiny contributor T, taking him well past his cap and more than doubling the total decayed burn amount. This roughly halves everyone else's burn shares and in particular pushes A, B, C,... back down to just under their caps. Now under the present algorithm, T gets capped in the first round and A, B, C,... get adjusted back up to a 22% burn share each. Then in the second round, they are capped at 11% each with the remaining 11% going to the LBM. In this way, the LBM could get much more than 11% total final share, say even 33% or more.In more concrete terms, suppose there is a total decayed burn amount of 250,000 BSQ -- this is close to the actual decayed burn amount as of the end of March 2023. Then the LBM could pick a tiny contributor T with a negligible issuance share (and cap) and three large contributors A, B and C, with decayed issuance share at least 1.1% each and thus caps of 11% each. He then burns up to 250,000 (1/0.34 - 1) / 3 ~= 161,765 BSQ on behalf of A, B and C each (though likely substantially less if they already have nonzero decayed burn amounts), to take each of them up to just under 22% burn share. This increases the total decayed burn amount to no more than 735,294 BSQ. Then the LBM burns another <735,294 BSQ on behalf of T to double the total and push the uncapped amounts of A, B and C back down to just under 11% each. After the second capping round, this leaves the LBM with at least 33% of the final DPT payout share, to complete his attack by sweeping the offer book and driving as many trades as possible into arbitration. So the LBM needs up to 250,000 (2/0.34 - 1) ~= 1,220,588 BSQ (plus BTC for security deposits) to carry out his attack, though likely substantially less.
(There are probably variants to the above example that are more efficient and don't need anywhere near 1.22 million BSQ.)
Proposed capping algorithm modification
To mitigate the two problems above, I propose applying an unlimited number of capping rounds, instead of just two. In each round, any (possibly already adjusted) shares that exceed their respective cap are capped and the subtracted share is distributed to the remaining uncapped contributors who are active burning men, if any, by further adjusting their shares upwards by a uniform scaling factor to reach a total of 100%. In the next round, some of those contributors may end up having exceeded their cap, so the process repeats with the set of uncapped contributors shrinking each round, until the set winds up empty. This will either be because every active burning man has been capped, in which case any remaining burn share goes to the LBM, or no further capping is necessary. In the latter case, some of the contributors will be capped and the remaining contributors (at least those with nonzero decayed burn amounts) will have had their shares scaled upwards uniformly to reach a total (capped + uncapped) of 100%, with the LBM getting nothing.
Thus with the proposed algorithm, the LBM gets a nonzero share (which could exceed 11%) precisely when the sum of the caps of all the active burning men is less than 100%. This will hopefully be rare, as preventing it only requires 9 or 10 active BM with a decayed issuance share greater than 1.1% each (or a large number of active BM with somewhat smaller issuance shares).
Note that the percentage going to the LBM (if any) is independent of the decayed burn amounts, under the modified algorithm, and only depends on the decayed issuance shares of the active burning men. Thus it is impossible for the LBM to increase their percentage by burning on behalf of other contributors -- they can only manipulate it downwards by burning on behalf of not yet active burning men, thus increasing the sum of the caps of the active burning men.
As of the end of March 2023, no one is being capped and certainly no contributor is being capped in the second round, so the algorithm change would hopefully not cause too much disruption. Perhaps the number of capping rounds could be increased from two to unlimited after a certain block height is reached.