Is pDEX fair?

Hey @Ducky,

Could you forward my question to the related devs?

I examine the code related to pDex request actions. In the end, I’ve reached that pDEX is not fair :slight_smile: for the trade requests within the same beacon height.

Here is the related code:
func categorizeNSortPDECrossPoolTradeInstsByFee() in beaconstatefulinsts.go

// sort tradable actions by trading fee
sort.Slice(tradableActions, func(i, j int) bool {
	firstTradingFee, firstSellAmount := prepareInfoForSorting(
		currentPDEState,
		beaconHeight,
		tradableActions[i],
	)
	secondTradingFee, secondSellAmount := prepareInfoForSorting(
		currentPDEState,
		beaconHeight,
		tradableActions[j],
	)
	// comparing a/b to c/d is equivalent with comparing a*d to c*b
	firstItemProportion := big.NewInt(0)
	firstItemProportion.Mul(
		new(big.Int).SetUint64(firstTradingFee),
		new(big.Int).SetUint64(secondSellAmount),
	)
	secondItemProportion := big.NewInt(0)
	secondItemProportion.Mul(
		new(big.Int).SetUint64(secondTradingFee),
		new(big.Int).SetUint64(firstSellAmount),
	)
	return firstItemProportion.Cmp(secondItemProportion) == 1
})
return tradableActions, untradableActions

How does this code work? Let me go through by an example (trade requests are sorted chronologically and they are in the blocks within the same beacon height):
Time : SellAmount --> MinAcceptableAmount
t0. sec : 100 PRV --> 1 BTC (T1)
t0+10. sec : 1 BTC --> 100 PRV (T2)
t0+20. sec : 100 PRV --> 1 BTC (T3)
t0+30. sec : 100 PRV --> 1 BTC (T4)

The shards of the trades do not matter here.

Currently, since the trading fee is zero (%0 percent), the multiplication of trading and sell amount is always equal to zero. What does it mean?firstItemProportion.Cmp(secondItemProportion) always returns 0 (https://golang.org/pkg/math/big/#Int.Cmp) since firstItemProportion and secondItemProportion are both zero. Then return firstItemProportion.Cmp(secondItemProportion) == 1 always returns false. In that case, someone expects that they would be executed chronologically. If this happens and we assume that the pool size respects our scenario,
T1 is accepted, T2 is accepted, T3 is accepted and then T4 is refunded since it requests more than the minimum acceptable amount.

However, I read the definition of sort.Slice function and run the example with different scenarios on that page (https://golang.org/pkg/sort/#Slice). Its sorting is not stable by definition. So, the requests may be executed in any order. For example,

T1 (accepted) --> T3 (refunded) --> T2 (accepted) --> T4 (accepted)

On the same page, there is sort.SliceStable function. However, it is not fair too since it is biased to the order in the array of the trade requests. So the order is determined how the dev fills up the array. For example, if she fills up the array with T1, T3, T4, T2 in a loop, then the requests will be executed in that order.

Finally, here is my question :slight_smile: In the absence of the trading fee, to make pDEX fair, is it possible and correct to use LockTime property of Txs to sort them chronologically?

Regards,

5 Likes

I took your question to our devs. Hope that someone could give an explanation soon.

1 Like

hi @abduraman, there will be more conditions for ordering trades if we wanted to make it sophisticated. But for simplicity, in the original design, in the same beacon block a trade tx would compete to other trade tx by trading fee (or proportion of trading fee and selling amount for more correctly). And when the DEX has more traders, I believe that people will increase the fee if they want their trade to be executed before the others.

Anyway, thanks for pointing it out, we’re considering to use sort.SliceStable to make more consistent and deterministic. Also, LockTime doesn’t solve the problem completely since txs are included in shard blocks and broadcasted to the beacon chain, so a tx with sooner LockTime is not always included (so executed) in a beacon block sooner than a later trade tx due to network latency.

2 Likes

Hey @duc,

As I stated, it is biased to how the dev writes the code. I have to examine the code more but up to now, I saw this. First, the dev groups the txs by shard id. Then she loops from smaller shard id to larger ones. In that case, two wrong things happen:
1- The txs in the same shard become atomic.
2- The txs in the smaller shard id become advantaged.

For example, let’s assume that T1, T4 are in the shard 0, T3 is in the shard 3 and T2 is in the shard 6.

The execution order will be T1, T4, T3 and T2. For example, I’m the owner of T3. Even if I add some trading fee, I cannot enter between T1 and T4 when they have the same fee (currently, it is zero). Either T3, T1, T4 or T1, T4, T3 can be executed. T1, T3, T4 is not possible.

You are right but the problem here is the txs in the same beacon block. I think LockTime solves the problem within the same block.

3 Likes

Hi again @duc,

Do you have a final decision on this issue and any ETA?

Thanks in advance.

According to the chain’s rules, the LockTime might be adjusted arbitrarily by tx creator as long as its value is less than now(), so one can set a very small LockTime in order to take advantage on the pdex if we order trades by LockTime. As I said, it does not solve the problem completely. And for now, we just decided to use sort.SliceStable to make sure the order is consistent among validators. Yes, it’s an open problem to discuss, we’ll be thinking really thoroughly before making any decision especially in a blockchain environment.

1 Like

Sorry, I did not understand it exactly. Will you implement sort.SliceStable soon? If so, any ETA? :slight_smile: @duc

Btw, because the usage of sort.Slice, incscan sometimes shows the trade order within the same beacon block incorrectly. FYI. @inccry Currently, you do not have any easy solution to fix it.

1 Like

I’m really appreciated your help in pointing it out, to be honest. sort.SliceStable will be deployed around next week. Updated the code, still working on QC to make sure it work perfectly. thanks again.

4 Likes

Hey @duc,

Was this deployed? If not, could you notify me when it is deployed? Thanks.

Since the update will be deployed along with the other updates in the same upgrade so it was be delayed a bit. Will let you know once it goes live (within this week for sure)

1 Like

Hey @duc,

I couldn’t decide which topic I should write. I prefer this topic.

@0xkumi wrote this in the other topic:

From this, I have understood that there is asynchronous but a one-to-one relationship between the shard block height and the beacon height. Today I tried to benefit from an arbitrage opportunity. The first tx request was on shard 0 with 740929 height and mine was on shard 0 with 740930. They were executed on the same beacon height (744524) and my tx was rejected (either due to sort.Slice or trading fee I added). If they were executed on the different beacon heights, my trade would be accepted. Then, I checked the situation via extractpdeinstsfrombeaconblock call. Yes, it was correct. So, is there a one-to-many relationship between the beacon and the same shard blocks? If so, can this presentation (https://incscan.io/blockchain/shard-blocks) be wrong? On that page, the shard 0 blocks 740929, 740930 are matched with the beacon blocks 744520, 744521 respectively. Or one-to-one relationship is correct but does pDEX process more than one beacon block simultaneously? If so, are there any frequency or some other criteria? This is my first question(s) :slight_smile:

The second question: Is there any RPC to get the execution order in pDEX? extractpdeinstsfrombeaconblock returns the trades but not the execution order. OK, I can infer some results from that but I need this to test my thoughts. I suspect a few issues.

Thanks.

Reminder :arrow_up: :slight_smile: @duc

Hey @abduraman, basically, the same beacon block processes multiple pdex instructions from multiple shard blocks (from multiple shards of course). And then these instructions would be ordered by trading fees. So it would not be a one-to-one relationship.

For the second question, I think extractpdeinstsfrombeaconblock rpc is returning processed pdex instructions in order already. By the way, sort.StableSlice has been deployed on Mainnet. Thanks.

1 Like

Hey @duc,

The code seems unchanged (https://github.com/incognitochain/incognito-chain/blob/62a4ed3287fb1f452b180d3df8fcc009240f73a1/blockchain/beaconstatefulinsts.go / func categorizeNSortPDECrossPoolTradeInstsByFee() ). Is there any delay between open-source and deployed code? If so, I think you’ve deployed today. Slice still was working yesterday. Am I right?

Thanks.

Ah please check out the branch: https://github.com/incognitochain/incognito-chain/tree/master-temp-B-deploy-consensus-v2-optimized
This is the branch we are using on Mainnet.

3 Likes

2 posts were merged into an existing topic: Pdex slippage issue feature request

Hey @duc,

The issue sometimes still occurs. I have examined the code again. This time I suspect the code block below at buildRelayingInstsFromActions() of https://github.com/incognitochain/incognito-chain/blob/master-temp-B-deploy-consensus-v2-optimized/blockchain/beaconrelayingproducer.go:

// sort blockHeightArr
sort.Slice(blockHeightArr, func(i, j int) bool {
	return blockHeightArr[i] < blockHeightArr[j]
})

Here, this unstable sorting may return the TXs in a different order than their coming order to the blockchain. I looked for all sort.Slice() in the source code. If I’m not wrong, it is used ~40 times. I think sort.Slice() is more efficient than sort.SliceStable(). Probably that’s why sort.Slice() is preferred unless some developers are not aware of sort.SliceStable(). As a suggestion, would you consider to replace each sort.Slice() by sort.SliceStable() to avoid future-bugs?

Best.

2 Likes

So how are trades sorted right now if they are in the same beacon block and have both the same trading fees?

1 Like

Not sure. As I wrote, since there are many sort.Slice() usages, the ordering of the items with equal attributes is not guaranteed by definition.

1 Like

I see. Maybe @duc can help us.

1 Like