Randomized choosing of orders by taker.

[chris-belcher]

Dont always pick the lowest cost order, instead have a probability density function that chooses them randomly. So most of the time you pick the lowest and sometimes you take higher ones this represents your uncertainty in sybil attackers, the cheapest may not always be the best i.e. randomly chosen makers, weighted by the price they offer

Need ideas for which form this PDF would take. Exponentially decaying probably, but with what decay constant?

[chris-belcher]

First implementation of randomized weighted order choosing.

https://github.com/chris-belcher/joinmarket/commit/63372f43332ddd799dadec899e52a75b863b8ad8

[chris-belcher]

Reopening this, another way to contribute to solving this problem is to quantize the prices before choosing. Within each quantum of orders the price is not considered, but the quantas are chosen based on price.

\<gmaxwell> Because the user doesn't truly have a meaningful preference over saving a single satoshi, and it would let an attacker capture more joins very cheaply just by auto-underbiding \<belcher> an attacker cant guarentee they'd join with everyone just by underbidding, since the choosing algorithm is random weighted by price rather than always choosing the cheapest \<gmaxwell> I do realize this. \<belcher> how do you suggest its implemented? maybe a price floor below which the taker doesnt consider the price anymore \<belcher> or the probability weighting having a longer tail so a larger variety of possibly more expensive orders are chosen \<gmaxwell> or more generally, having the taker quantize the prices before continuing with your current weighed algorithim. \<belcher> ah so within each grouping of orders the price is not considered, but between groupings are chosen based on price \<gmaxwell> It's something no different than lots of other kinds of markets have done to prevent front-running... \<gmaxwell> though your randomization makes the front running less bad, it doesn't eliminate it is... at least you can make it so that if you're going to get a preference advantage you're actually charging a 'meaninfully' smaller amount. \<belcher> no i agree with the principle \<belcher> its a good idea, i never thought of it in terms of front running like from flash boys \<gmaxwell> belcher: does JM preference new maker coins? e.g. if someone is a regular maker their coins will cycle through many CJs and effectively make their CJ's less anonymous. \<belcher> it does not \<belcher> gmaxwell do you know how the sizes of those quanta are chosen in other markets ? \<belcher> that make front running harder \<belcher> a constant number of satoshi, how many satoshi or a constant ratio of satoshi, and what ratio \<belcher> maybe set that each quanta contains X number of makers, maybe X= 2N where N is the number you wanted to coinjoin with \<gmaxwell> In your case the precision doesn't even need to be normative. In that the taker can just decide how he evaluates the offers. \<belcher> yeah i was thinking of implementing it that way, that the quanta exist in the taker's script not in the market \<belcher> each taker can have their own sized quanta \<gmaxwell> AFAICT in stock and futures markets there is nothing rigoursly done.. because of inflation historic high precision because too coarse over time, and then precision gets updated due to market pressure. \<belcher> essentially quanta should be the size of a "meaningful" price change \<gmaxwell> Right. I don't think it requires too much advanced though .. in the sense that the value could be off by an order of magnitude in either direction and still work fine. \<belcher> the current way where a random order is chosen weighted by price also has a ton of magic numbers, it seems to work ok

[chris-belcher]

A normal bitcoin exchange doing increasing the size of their ticks for the same reason as the quanization idea: https://www.reddit.com/r/BitcoinMarkets/comments/4tmp4c/coinfloor_changes_tick_size_to_1_gbp/

[DavidVorick]

My understanding is that the random weighting is sufficient, depending on how you've implemented it. It's pretty similar to the problem of selecting hosts in Sia.

The weightings that we've set up exponentially prefer lower prices. Meaning, 1/2 price results in a 32x weighting for the host. Even with such a large exponent, small undercutting doesn't do much. Someone trying to front-run by reducing their price by 1% is only going to have a 5% increased weight. In my eyes, the reduced price merits that increased weight, and doesn't present a front-running risk. Quantization doesn't seem necessary given the random weighting.

You may still want to have a floor that counts as 'effectively free' though, I'm not sure that the difference between 1 satoshi and 2 satoshis and 5 satoshis should be exponentially different.

I wonder if an exchange has ever chosen to fill orders probabilistically instead of by manipulating the tick size?

[DavidVorick]

Thinking about the price floor a little more, there is a meaningful difference between 1, 2, and 5 satoshis, in that you can do 5x the number of joins at a cost of 1 satoshi than at the cost of 5 satoshis before you hit the 'effectively free' price, which means you can increase security at the same cost by joining with more people.

If the software is set up to always select N people to join with, then having a price floor makes sense. But if N can increase by the number of 'effectively costless to add' participants, then it makes sense to place higher weightings on cheaper parties. That does require a smarter client.

Every transaction has to pay transaction fees though. When doing a join with someone, you should include the cost of the transaction fees into their price, and that will set a floor.