From 14fdb71a716cb95bc1f6933db9057d23f3c41909 Mon Sep 17 00:00:00 2001 From: Amir Bandeali Date: Tue, 28 Aug 2018 13:00:49 -0700 Subject: safeGetPartialAmount (#1035) * Added Test "Should transfer correct amounts when left order is fully filled and values pass isRoundingErrorCeil but fail isRoundingErrorFloor" * Added RoundingError exception to reference function for getPartialAmount * Added RoundingError exception to reference function for getPartialAmount * Added isRoundingErrorCeil to getPartialAmountCeil reference funtion * Computed new values for "Should give right maker a better buy price when correct price is not integral" that does not have a rounding error * Almost all tests for match orders are passing after adding isRoundingErrorCeil check * WIP commit: Added rounding error checks to getPartialAmount * WIP commit: Added rounding error checks to getPartialAmount * Use safe versions of getPartialAmount * Update Exchange internals tests * Run linter * Found new values for "Should transfer correct amounts when right order fill amount deviates from amount derived by `Exchange.fillOrder`" * Fixed merge conflicts * Run all tests * Cleaned up some comments on match Orders tests * Fix tests for geth --- .../2.0.0/protocol/Exchange/MixinExchangeCore.sol | 16 +- .../2.0.0/protocol/Exchange/MixinMatchOrders.sol | 16 +- .../src/2.0.0/protocol/Exchange/libs/LibMath.sol | 82 +++++++- .../ReentrantERC20Token/ReentrantERC20Token.sol | 1 + .../TestExchangeInternals.sol | 36 ++++ packages/contracts/test/exchange/internal.ts | 181 ++++++++++++----- packages/contracts/test/exchange/match_orders.ts | 220 +++++++++++++++++---- 7 files changed, 442 insertions(+), 110 deletions(-) diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol b/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol index be163ec97..64b1f7665 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/MixinExchangeCore.sol @@ -404,16 +404,6 @@ contract MixinExchangeCore is safeMul(order.makerAssetAmount, takerAssetFilledAmount), "INVALID_FILL_PRICE" ); - - // Validate fill order rounding - require( - !isRoundingErrorFloor( - takerAssetFilledAmount, - order.takerAssetAmount, - order.makerAssetAmount - ), - "ROUNDING_ERROR" - ); } /// @dev Validates context for cancelOrder. Succeeds or throws. @@ -463,17 +453,17 @@ contract MixinExchangeCore is { // Compute proportional transfer amounts fillResults.takerAssetFilledAmount = takerAssetFilledAmount; - fillResults.makerAssetFilledAmount = getPartialAmountFloor( + fillResults.makerAssetFilledAmount = safeGetPartialAmountFloor( takerAssetFilledAmount, order.takerAssetAmount, order.makerAssetAmount ); - fillResults.makerFeePaid = getPartialAmountFloor( + fillResults.makerFeePaid = safeGetPartialAmountFloor( takerAssetFilledAmount, order.takerAssetAmount, order.makerFee ); - fillResults.takerFeePaid = getPartialAmountFloor( + fillResults.takerFeePaid = safeGetPartialAmountFloor( takerAssetFilledAmount, order.takerAssetAmount, order.takerFee diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol b/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol index 075a610b5..b4f6bdb26 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/MixinMatchOrders.sol @@ -177,13 +177,13 @@ contract MixinMatchOrders is { // Derive maker asset amounts for left & right orders, given store taker assert amounts uint256 leftTakerAssetAmountRemaining = safeSub(leftOrder.takerAssetAmount, leftOrderTakerAssetFilledAmount); - uint256 leftMakerAssetAmountRemaining = getPartialAmountFloor( + uint256 leftMakerAssetAmountRemaining = safeGetPartialAmountFloor( leftOrder.makerAssetAmount, leftOrder.takerAssetAmount, leftTakerAssetAmountRemaining ); uint256 rightTakerAssetAmountRemaining = safeSub(rightOrder.takerAssetAmount, rightOrderTakerAssetFilledAmount); - uint256 rightMakerAssetAmountRemaining = getPartialAmountFloor( + uint256 rightMakerAssetAmountRemaining = safeGetPartialAmountFloor( rightOrder.makerAssetAmount, rightOrder.takerAssetAmount, rightTakerAssetAmountRemaining @@ -205,7 +205,7 @@ contract MixinMatchOrders is matchedFillResults.left.takerAssetFilledAmount = matchedFillResults.right.makerAssetFilledAmount; // Round down to ensure the maker's exchange rate does not exceed the price specified by the order. // We favor the maker when the exchange rate must be rounded. - matchedFillResults.left.makerAssetFilledAmount = getPartialAmountFloor( + matchedFillResults.left.makerAssetFilledAmount = safeGetPartialAmountFloor( leftOrder.makerAssetAmount, leftOrder.takerAssetAmount, matchedFillResults.left.takerAssetFilledAmount @@ -217,7 +217,7 @@ contract MixinMatchOrders is matchedFillResults.right.makerAssetFilledAmount = matchedFillResults.left.takerAssetFilledAmount; // Round up to ensure the maker's exchange rate does not exceed the price specified by the order. // We favor the maker when the exchange rate must be rounded. - matchedFillResults.right.takerAssetFilledAmount = getPartialAmountCeil( + matchedFillResults.right.takerAssetFilledAmount = safeGetPartialAmountCeil( rightOrder.takerAssetAmount, rightOrder.makerAssetAmount, matchedFillResults.right.makerAssetFilledAmount @@ -231,24 +231,24 @@ contract MixinMatchOrders is ); // Compute fees for left order - matchedFillResults.left.makerFeePaid = getPartialAmountFloor( + matchedFillResults.left.makerFeePaid = safeGetPartialAmountFloor( matchedFillResults.left.makerAssetFilledAmount, leftOrder.makerAssetAmount, leftOrder.makerFee ); - matchedFillResults.left.takerFeePaid = getPartialAmountFloor( + matchedFillResults.left.takerFeePaid = safeGetPartialAmountFloor( matchedFillResults.left.takerAssetFilledAmount, leftOrder.takerAssetAmount, leftOrder.takerFee ); // Compute fees for right order - matchedFillResults.right.makerFeePaid = getPartialAmountFloor( + matchedFillResults.right.makerFeePaid = safeGetPartialAmountFloor( matchedFillResults.right.makerAssetFilledAmount, rightOrder.makerAssetAmount, rightOrder.makerFee ); - matchedFillResults.right.takerFeePaid = getPartialAmountFloor( + matchedFillResults.right.takerFeePaid = safeGetPartialAmountFloor( matchedFillResults.right.takerAssetFilledAmount, rightOrder.takerAssetAmount, rightOrder.takerFee diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index 0e0fba5d2..57fd53f29 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -26,11 +26,48 @@ contract LibMath is { /// @dev Calculates partial value given a numerator and denominator rounded down. + /// Reverts if rounding error is >= 0.1% /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to calculate partial of. /// @return Partial value of target rounded down. - function getPartialAmountFloor( + function safeGetPartialAmountFloor( + uint256 numerator, + uint256 denominator, + uint256 target + ) + internal + pure + returns (uint256 partialAmount) + { + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); + + require( + !isRoundingErrorFloor( + numerator, + denominator, + target + ), + "ROUNDING_ERROR" + ); + + partialAmount = safeDiv( + safeMul(numerator, target), + denominator + ); + return partialAmount; + } + + /// @dev Calculates partial value given a numerator and denominator rounded down. + /// Reverts if rounding error is >= 0.1% + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to calculate partial of. + /// @return Partial value of target rounded up. + function safeGetPartialAmountCeil( uint256 numerator, uint256 denominator, uint256 target @@ -43,7 +80,48 @@ contract LibMath is denominator > 0, "DIVISION_BY_ZERO" ); + + require( + !isRoundingErrorCeil( + numerator, + denominator, + target + ), + "ROUNDING_ERROR" + ); + // safeDiv computes `floor(a / b)`. We use the identity (a, b integer): + // ceil(a / b) = floor((a + b - 1) / b) + // To implement `ceil(a / b)` using safeDiv. + partialAmount = safeDiv( + safeAdd( + safeMul(numerator, target), + safeSub(denominator, 1) + ), + denominator + ); + return partialAmount; + } + + /// @dev Calculates partial value given a numerator and denominator rounded down. + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to calculate partial of. + /// @return Partial value of target rounded down. + function getPartialAmountFloor( + uint256 numerator, + uint256 denominator, + uint256 target + ) + internal + pure + returns (uint256 partialAmount) + { + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); + partialAmount = safeDiv( safeMul(numerator, target), denominator @@ -69,7 +147,7 @@ contract LibMath is denominator > 0, "DIVISION_BY_ZERO" ); - + // safeDiv computes `floor(a / b)`. We use the identity (a, b integer): // ceil(a / b) = floor((a + b - 1) / b) // To implement `ceil(a / b)` using safeDiv. diff --git a/packages/contracts/src/2.0.0/test/ReentrantERC20Token/ReentrantERC20Token.sol b/packages/contracts/src/2.0.0/test/ReentrantERC20Token/ReentrantERC20Token.sol index 8bfdd2e66..4f4e28302 100644 --- a/packages/contracts/src/2.0.0/test/ReentrantERC20Token/ReentrantERC20Token.sol +++ b/packages/contracts/src/2.0.0/test/ReentrantERC20Token/ReentrantERC20Token.sol @@ -25,6 +25,7 @@ import "../../protocol/Exchange/interfaces/IExchange.sol"; import "../../protocol/Exchange/libs/LibOrder.sol"; +// solhint-disable no-unused-vars contract ReentrantERC20Token is ERC20Token { diff --git a/packages/contracts/src/2.0.0/test/TestExchangeInternals/TestExchangeInternals.sol b/packages/contracts/src/2.0.0/test/TestExchangeInternals/TestExchangeInternals.sol index da9313e02..27187f8f8 100644 --- a/packages/contracts/src/2.0.0/test/TestExchangeInternals/TestExchangeInternals.sol +++ b/packages/contracts/src/2.0.0/test/TestExchangeInternals/TestExchangeInternals.sol @@ -62,6 +62,42 @@ contract TestExchangeInternals is return calculateFillResults(order, takerAssetFilledAmount); } + /// @dev Calculates partial value given a numerator and denominator. + /// Reverts if rounding error is >= 0.1% + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to calculate partial of. + /// @return Partial value of target. + function publicSafeGetPartialAmountFloor( + uint256 numerator, + uint256 denominator, + uint256 target + ) + public + pure + returns (uint256 partialAmount) + { + return safeGetPartialAmountFloor(numerator, denominator, target); + } + + /// @dev Calculates partial value given a numerator and denominator. + /// Reverts if rounding error is >= 0.1% + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to calculate partial of. + /// @return Partial value of target. + function publicSafeGetPartialAmountCeil( + uint256 numerator, + uint256 denominator, + uint256 target + ) + public + pure + returns (uint256 partialAmount) + { + return safeGetPartialAmountCeil(numerator, denominator, target); + } + /// @dev Calculates partial value given a numerator and denominator. /// @param numerator Numerator. /// @param denominator Denominator. diff --git a/packages/contracts/test/exchange/internal.ts b/packages/contracts/test/exchange/internal.ts index de381fca3..c5d2fc58f 100644 --- a/packages/contracts/test/exchange/internal.ts +++ b/packages/contracts/test/exchange/internal.ts @@ -48,9 +48,9 @@ const overflowErrorForCall = new Error(RevertReason.Uint256Overflow); describe('Exchange core internal functions', () => { let testExchange: TestExchangeInternalsContract; - let invalidOpcodeErrorForCall: Error | undefined; let overflowErrorForSendTransaction: Error | undefined; let divisionByZeroErrorForCall: Error | undefined; + let roundingErrorForCall: Error | undefined; before(async () => { await blockchainLifecycle.startAsync(); @@ -68,12 +68,67 @@ describe('Exchange core internal functions', () => { await getRevertReasonOrErrorMessageForSendTransactionAsync(RevertReason.Uint256Overflow), ); divisionByZeroErrorForCall = new Error(RevertReason.DivisionByZero); - invalidOpcodeErrorForCall = new Error(await getInvalidOpcodeErrorMessageForCallAsync()); + roundingErrorForCall = new Error(RevertReason.RoundingError); }); // Note(albrow): Don't forget to add beforeEach and afterEach calls to reset // the blockchain state for any tests which modify it! - async function referenceGetPartialAmountFloorAsync( + async function referenceIsRoundingErrorFloorAsync( + numerator: BigNumber, + denominator: BigNumber, + target: BigNumber, + ): Promise { + if (denominator.eq(0)) { + throw divisionByZeroErrorForCall; + } + if (numerator.eq(0)) { + return false; + } + if (target.eq(0)) { + return false; + } + const product = numerator.mul(target); + const remainder = product.mod(denominator); + const remainderTimes1000 = remainder.mul('1000'); + const isError = remainderTimes1000.gte(product); + if (product.greaterThan(MAX_UINT256)) { + throw overflowErrorForCall; + } + if (remainderTimes1000.greaterThan(MAX_UINT256)) { + throw overflowErrorForCall; + } + return isError; + } + + async function referenceIsRoundingErrorCeilAsync( + numerator: BigNumber, + denominator: BigNumber, + target: BigNumber, + ): Promise { + if (denominator.eq(0)) { + throw divisionByZeroErrorForCall; + } + if (numerator.eq(0)) { + return false; + } + if (target.eq(0)) { + return false; + } + const product = numerator.mul(target); + const remainder = product.mod(denominator); + const error = denominator.sub(remainder).mod(denominator); + const errorTimes1000 = error.mul('1000'); + const isError = errorTimes1000.gte(product); + if (product.greaterThan(MAX_UINT256)) { + throw overflowErrorForCall; + } + if (errorTimes1000.greaterThan(MAX_UINT256)) { + throw overflowErrorForCall; + } + return isError; + } + + async function referenceSafeGetPartialAmountFloorAsync( numerator: BigNumber, denominator: BigNumber, target: BigNumber, @@ -81,6 +136,10 @@ describe('Exchange core internal functions', () => { if (denominator.eq(0)) { throw divisionByZeroErrorForCall; } + const isRoundingError = await referenceIsRoundingErrorFloorAsync(numerator, denominator, target); + if (isRoundingError) { + throw roundingErrorForCall; + } const product = numerator.mul(target); if (product.greaterThan(MAX_UINT256)) { throw overflowErrorForCall; @@ -163,18 +222,18 @@ describe('Exchange core internal functions', () => { // implementation or the Solidity implementation of // calculateFillResults. return { - makerAssetFilledAmount: await referenceGetPartialAmountFloorAsync( + makerAssetFilledAmount: await referenceSafeGetPartialAmountFloorAsync( takerAssetFilledAmount, orderTakerAssetAmount, otherAmount, ), takerAssetFilledAmount, - makerFeePaid: await referenceGetPartialAmountFloorAsync( + makerFeePaid: await referenceSafeGetPartialAmountFloorAsync( takerAssetFilledAmount, orderTakerAssetAmount, otherAmount, ), - takerFeePaid: await referenceGetPartialAmountFloorAsync( + takerFeePaid: await referenceSafeGetPartialAmountFloorAsync( takerAssetFilledAmount, orderTakerAssetAmount, otherAmount, @@ -198,6 +257,20 @@ describe('Exchange core internal functions', () => { }); describe('getPartialAmountFloor', async () => { + async function referenceGetPartialAmountFloorAsync( + numerator: BigNumber, + denominator: BigNumber, + target: BigNumber, + ): Promise { + if (denominator.eq(0)) { + throw divisionByZeroErrorForCall; + } + const product = numerator.mul(target); + if (product.greaterThan(MAX_UINT256)) { + throw overflowErrorForCall; + } + return product.dividedToIntegerBy(denominator); + } async function testGetPartialAmountFloorAsync( numerator: BigNumber, denominator: BigNumber, @@ -206,7 +279,7 @@ describe('Exchange core internal functions', () => { return testExchange.publicGetPartialAmountFloor.callAsync(numerator, denominator, target); } await testCombinatoriallyWithReferenceFuncAsync( - 'getPartialAmount', + 'getPartialAmountFloor', referenceGetPartialAmountFloorAsync, testGetPartialAmountFloorAsync, [uint256Values, uint256Values, uint256Values], @@ -250,76 +323,80 @@ describe('Exchange core internal functions', () => { ); }); - describe('isRoundingError', async () => { - async function referenceIsRoundingErrorAsync( + describe('safeGetPartialAmountFloor', async () => { + async function testSafeGetPartialAmountFloorAsync( numerator: BigNumber, denominator: BigNumber, target: BigNumber, - ): Promise { + ): Promise { + return testExchange.publicSafeGetPartialAmountFloor.callAsync(numerator, denominator, target); + } + await testCombinatoriallyWithReferenceFuncAsync( + 'safeGetPartialAmountFloor', + referenceSafeGetPartialAmountFloorAsync, + testSafeGetPartialAmountFloorAsync, + [uint256Values, uint256Values, uint256Values], + ); + }); + + describe('safeGetPartialAmountCeil', async () => { + async function referenceSafeGetPartialAmountCeilAsync( + numerator: BigNumber, + denominator: BigNumber, + target: BigNumber, + ): Promise { if (denominator.eq(0)) { throw divisionByZeroErrorForCall; } - if (numerator.eq(0)) { - return false; - } - if (target.eq(0)) { - return false; + const isRoundingError = await referenceIsRoundingErrorCeilAsync(numerator, denominator, target); + if (isRoundingError) { + throw roundingErrorForCall; } const product = numerator.mul(target); - const remainder = product.mod(denominator); - const remainderTimes1000 = remainder.mul('1000'); - const isError = remainderTimes1000.gt(product); - if (product.greaterThan(MAX_UINT256)) { + const offset = product.add(denominator.sub(1)); + if (offset.greaterThan(MAX_UINT256)) { throw overflowErrorForCall; } - if (remainderTimes1000.greaterThan(MAX_UINT256)) { - throw overflowErrorForCall; + const result = offset.dividedToIntegerBy(denominator); + if (product.mod(denominator).eq(0)) { + expect(result.mul(denominator)).to.be.bignumber.eq(product); + } else { + expect(result.mul(denominator)).to.be.bignumber.gt(product); } - return isError; + return result; } - async function testIsRoundingErrorAsync( + async function testSafeGetPartialAmountCeilAsync( numerator: BigNumber, denominator: BigNumber, target: BigNumber, - ): Promise { - return testExchange.publicIsRoundingErrorFloor.callAsync(numerator, denominator, target); + ): Promise { + return testExchange.publicSafeGetPartialAmountCeil.callAsync(numerator, denominator, target); } await testCombinatoriallyWithReferenceFuncAsync( - 'isRoundingError', - referenceIsRoundingErrorAsync, - testIsRoundingErrorAsync, + 'safeGetPartialAmountCeil', + referenceSafeGetPartialAmountCeilAsync, + testSafeGetPartialAmountCeilAsync, [uint256Values, uint256Values, uint256Values], ); }); - describe('isRoundingErrorCeil', async () => { - async function referenceIsRoundingErrorAsync( + describe('isRoundingErrorFloor', async () => { + async function testIsRoundingErrorFloorAsync( numerator: BigNumber, denominator: BigNumber, target: BigNumber, ): Promise { - if (denominator.eq(0)) { - throw divisionByZeroErrorForCall; - } - if (numerator.eq(0)) { - return false; - } - if (target.eq(0)) { - return false; - } - const product = numerator.mul(target); - const remainder = product.mod(denominator); - const error = denominator.sub(remainder).mod(denominator); - const errorTimes1000 = error.mul('1000'); - const isError = errorTimes1000.gt(product); - if (product.greaterThan(MAX_UINT256)) { - throw overflowErrorForCall; - } - if (errorTimes1000.greaterThan(MAX_UINT256)) { - throw overflowErrorForCall; - } - return isError; + return testExchange.publicIsRoundingErrorFloor.callAsync(numerator, denominator, target); } + await testCombinatoriallyWithReferenceFuncAsync( + 'isRoundingErrorFloor', + referenceIsRoundingErrorFloorAsync, + testIsRoundingErrorFloorAsync, + [uint256Values, uint256Values, uint256Values], + ); + }); + + describe('isRoundingErrorCeil', async () => { async function testIsRoundingErrorCeilAsync( numerator: BigNumber, denominator: BigNumber, @@ -329,7 +406,7 @@ describe('Exchange core internal functions', () => { } await testCombinatoriallyWithReferenceFuncAsync( 'isRoundingErrorCeil', - referenceIsRoundingErrorAsync, + referenceIsRoundingErrorCeilAsync, testIsRoundingErrorCeilAsync, [uint256Values, uint256Values, uint256Values], ); diff --git a/packages/contracts/test/exchange/match_orders.ts b/packages/contracts/test/exchange/match_orders.ts index 8732e20ba..554c456cc 100644 --- a/packages/contracts/test/exchange/match_orders.ts +++ b/packages/contracts/test/exchange/match_orders.ts @@ -3,6 +3,7 @@ import { assetDataUtils } from '@0xproject/order-utils'; import { RevertReason } from '@0xproject/types'; import { BigNumber } from '@0xproject/utils'; import { Web3Wrapper } from '@0xproject/web3-wrapper'; +import * as chai from 'chai'; import * as _ from 'lodash'; import { DummyERC20TokenContract } from '../../generated_contract_wrappers/dummy_erc20_token'; @@ -11,8 +12,10 @@ import { ERC20ProxyContract } from '../../generated_contract_wrappers/erc20_prox import { ERC721ProxyContract } from '../../generated_contract_wrappers/erc721_proxy'; import { ExchangeContract } from '../../generated_contract_wrappers/exchange'; import { ReentrantERC20TokenContract } from '../../generated_contract_wrappers/reentrant_erc20_token'; +import { TestExchangeInternalsContract } from '../../generated_contract_wrappers/test_exchange_internals'; import { artifacts } from '../utils/artifacts'; import { expectTransactionFailedAsync } from '../utils/assertions'; +import { chaiSetup } from '../utils/chai_setup'; import { constants } from '../utils/constants'; import { ERC20Wrapper } from '../utils/erc20_wrapper'; import { ERC721Wrapper } from '../utils/erc721_wrapper'; @@ -23,6 +26,8 @@ import { ERC20BalancesByOwner, ERC721TokenIdsByOwner } from '../utils/types'; import { provider, txDefaults, web3Wrapper } from '../utils/web3_wrapper'; const blockchainLifecycle = new BlockchainLifecycle(web3Wrapper); +chaiSetup.configure(); +const expect = chai.expect; describe('matchOrders', () => { let makerAddressLeft: string; @@ -58,6 +63,8 @@ describe('matchOrders', () => { let matchOrderTester: MatchOrderTester; + let testExchange: TestExchangeInternalsContract; + before(async () => { await blockchainLifecycle.startAsync(); }); @@ -160,6 +167,11 @@ describe('matchOrders', () => { orderFactoryRight = new OrderFactory(privateKeyRight, defaultOrderParamsRight); // Set match order tester matchOrderTester = new MatchOrderTester(exchangeWrapper, erc20Wrapper, erc721Wrapper, zrxToken.address); + testExchange = await TestExchangeInternalsContract.deployFrom0xArtifactAsync( + artifacts.TestExchangeInternals, + provider, + txDefaults, + ); }); beforeEach(async () => { await blockchainLifecycle.startAsync(); @@ -173,39 +185,170 @@ describe('matchOrders', () => { erc721TokenIdsByOwner = await erc721Wrapper.getBalancesAsync(); }); - it('Should give right maker a better price when correct price is not integral', async () => { + it('Should transfer correct amounts when right order is fully filled and values pass isRoundingErrorFloor but fail isRoundingErrorCeil', async () => { + // Create orders to match + const signedOrderLeft = await orderFactoryLeft.newSignedOrderAsync({ + makerAddress: makerAddressLeft, + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(17), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(98), 0), + feeRecipientAddress: feeRecipientAddressLeft, + }); + const signedOrderRight = await orderFactoryRight.newSignedOrderAsync({ + makerAddress: makerAddressRight, + makerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20TakerAssetAddress), + takerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20MakerAssetAddress), + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(75), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(13), 0), + feeRecipientAddress: feeRecipientAddressRight, + }); + // Assert is rounding error ceil & not rounding error floor + // These assertions are taken from MixinMatchOrders::calculateMatchedFillResults + // The rounding error is derived computating how much the left maker will sell. + const numerator = signedOrderLeft.makerAssetAmount; + const denominator = signedOrderLeft.takerAssetAmount; + const target = signedOrderRight.makerAssetAmount; + const isRoundingErrorCeil = await testExchange.publicIsRoundingErrorCeil.callAsync( + numerator, + denominator, + target, + ); + expect(isRoundingErrorCeil).to.be.true(); + const isRoundingErrorFloor = await testExchange.publicIsRoundingErrorFloor.callAsync( + numerator, + denominator, + target, + ); + expect(isRoundingErrorFloor).to.be.false(); + // Match signedOrderLeft with signedOrderRight + // Note that the left maker received a slightly better sell price. + // This is intentional; see note in MixinMatchOrders.calculateMatchedFillResults. + // Because the left maker received a slightly more favorable sell price, the fee + // paid by the left taker is slightly higher than that paid by the left maker. + // Fees can be thought of as a tax paid by the seller, derived from the sale price. + const expectedTransferAmounts = { + // Left Maker + amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(13), 0), + amountBoughtByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(75), 0), + feePaidByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber('76.4705882352941176'), 16), // 76.47% + // Right Maker + amountSoldByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(75), 0), + amountBoughtByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(13), 0), + feePaidByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% + // Taker + amountReceivedByTaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(0), 0), + feePaidByTakerLeft: Web3Wrapper.toBaseUnitAmount(new BigNumber('76.5306122448979591'), 16), // 76.53% + feePaidByTakerRight: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% + }; + await matchOrderTester.matchOrdersAndAssertEffectsAsync( + signedOrderLeft, + signedOrderRight, + takerAddress, + erc20BalancesByOwner, + erc721TokenIdsByOwner, + expectedTransferAmounts, + ); + }); + + it('Should transfer correct amounts when left order is fully filled and values pass isRoundingErrorCeil but fail isRoundingErrorFloor', async () => { + // Create orders to match + const signedOrderLeft = await orderFactoryLeft.newSignedOrderAsync({ + makerAddress: makerAddressLeft, + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(15), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(90), 0), + feeRecipientAddress: feeRecipientAddressLeft, + }); + const signedOrderRight = await orderFactoryRight.newSignedOrderAsync({ + makerAddress: makerAddressRight, + makerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20TakerAssetAddress), + takerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20MakerAssetAddress), + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(97), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(14), 0), + feeRecipientAddress: feeRecipientAddressRight, + }); + // Assert is rounding error floor & not rounding error ceil + // These assertions are taken from MixinMatchOrders::calculateMatchedFillResults + // The rounding error is derived computating how much the right maker will buy. + const numerator = signedOrderRight.takerAssetAmount; + const denominator = signedOrderRight.makerAssetAmount; + const target = signedOrderLeft.takerAssetAmount; + const isRoundingErrorFloor = await testExchange.publicIsRoundingErrorFloor.callAsync( + numerator, + denominator, + target, + ); + expect(isRoundingErrorFloor).to.be.true(); + const isRoundingErrorCeil = await testExchange.publicIsRoundingErrorCeil.callAsync( + numerator, + denominator, + target, + ); + expect(isRoundingErrorCeil).to.be.false(); + // Match signedOrderLeft with signedOrderRight + // Note that the right maker received a slightly better purchase price. + // This is intentional; see note in MixinMatchOrders.calculateMatchedFillResults. + // Because the right maker received a slightly more favorable buy price, the fee + // paid by the right taker is slightly higher than that paid by the right maker. + // Fees can be thought of as a tax paid by the seller, derived from the sale price. + const expectedTransferAmounts = { + // Left Maker + amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(15), 0), + amountBoughtByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(90), 0), + feePaidByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% + // Right Maker + amountSoldByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(90), 0), + amountBoughtByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(13), 0), + feePaidByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber('92.7835051546391752'), 16), // 92.78% + // Taker + amountReceivedByTaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(2), 0), + feePaidByTakerLeft: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% + feePaidByTakerRight: Web3Wrapper.toBaseUnitAmount(new BigNumber('92.8571428571428571'), 16), // 92.85% + }; + await matchOrderTester.matchOrdersAndAssertEffectsAsync( + signedOrderLeft, + signedOrderRight, + takerAddress, + erc20BalancesByOwner, + erc721TokenIdsByOwner, + expectedTransferAmounts, + ); + }); + + it('Should give right maker a better buy price when rounding', async () => { // Create orders to match const signedOrderLeft = await orderFactoryLeft.newSignedOrderAsync({ makerAddress: makerAddressLeft, - makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(2000), 0), - takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(1001), 0), + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(16), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(22), 0), feeRecipientAddress: feeRecipientAddressLeft, }); const signedOrderRight = await orderFactoryRight.newSignedOrderAsync({ makerAddress: makerAddressRight, makerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20TakerAssetAddress), takerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20MakerAssetAddress), - makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(10000), 0), - takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(3000), 0), + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(83), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(49), 0), feeRecipientAddress: feeRecipientAddressRight, }); // Note: + // The correct price buy price for the right maker would yield (49/83) * 22 = 12.988 units + // of the left maker asset. This gets rounded up to 13, giving the right maker a better price. + // Note: // The maker/taker fee percentage paid on the right order differs because - // they received different sale prices. Similarly, the right maker pays a - // slightly higher lower than the right taker. + // they received different sale prices. The right maker pays a + // fee slightly lower than the right taker. const expectedTransferAmounts = { // Left Maker - amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(2000), 0), - amountBoughtByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(1001), 0), + amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(16), 0), + amountBoughtByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(22), 0), feePaidByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% // Right Maker - amountSoldByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(1001), 0), - amountBoughtByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(301), 0), - feePaidByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(10.01), 16), // 10.01% + amountSoldByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(22), 0), + amountBoughtByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(13), 0), + feePaidByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber('26.5060240963855421'), 16), // 26.506% // Taker - amountReceivedByTaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(1699), 0), + amountReceivedByTaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(3), 0), feePaidByTakerLeft: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% - feePaidByTakerRight: Web3Wrapper.toBaseUnitAmount(new BigNumber('10.0333333333333333'), 16), // 10.03% + feePaidByTakerRight: Web3Wrapper.toBaseUnitAmount(new BigNumber('26.5306122448979591'), 16), // 26.531% }; // Match signedOrderLeft with signedOrderRight await matchOrderTester.matchOrdersAndAssertEffectsAsync( @@ -218,7 +361,7 @@ describe('matchOrders', () => { ); }); - it('Should give left maker a better price when correct price is not integral', async () => { + it('Should give left maker a better sell price when rounding', async () => { // Create orders to match const signedOrderLeft = await orderFactoryLeft.newSignedOrderAsync({ makerAddress: makerAddressLeft, @@ -236,7 +379,8 @@ describe('matchOrders', () => { }); // Note: // The maker/taker fee percentage paid on the left order differs because - // they received different sale prices. + // they received different sale prices. The left maker pays a fee + // slightly lower than the left taker. const expectedTransferAmounts = { // Left Maker amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(11), 0), @@ -266,39 +410,45 @@ describe('matchOrders', () => { // Create orders to match const signedOrderLeft = await orderFactoryLeft.newSignedOrderAsync({ makerAddress: makerAddressLeft, - makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(10), 0), - takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(3), 0), + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(1000), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(1005), 0), feeRecipientAddress: feeRecipientAddressLeft, }); const signedOrderRight = await orderFactoryRight.newSignedOrderAsync({ makerAddress: makerAddressRight, makerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20TakerAssetAddress), takerAssetData: assetDataUtils.encodeERC20AssetData(defaultERC20MakerAssetAddress), - makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(4), 0), - takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(2), 0), + makerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(2126), 0), + takerAssetAmount: Web3Wrapper.toBaseUnitAmount(new BigNumber(1063), 0), feeRecipientAddress: feeRecipientAddressRight, }); - // TODO: These values will change after implementation of rounding up has been merged const expectedTransferAmounts = { // Left Maker - amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(10), 0), - amountBoughtByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(3), 0), + amountSoldByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(1000), 0), + amountBoughtByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(1005), 0), feePaidByLeftMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% // Right Maker - // Note: - // For order [4,2] valid fill amounts through `Exchange.fillOrder` would be [2, 1] or [4, 2] - // In this case we have fill amounts of [3, 1] which is attainable through - // `Exchange.matchOrders` but not `Exchange.fillOrder` - // Note: - // The right maker fee differs from the right taker fee because their exchange rate differs. - // The right maker always receives the better exchange and fee price. - amountSoldByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(3), 0), - amountBoughtByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(2), 0), - feePaidByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(75), 16), // 75% + // Notes: + // i. + // The left order is fully filled by the right order, so the right maker must sell 1005 units of their asset to the left maker. + // By selling 1005 units, the right maker should theoretically receive 502.5 units of the left maker's asset. + // Since the transfer amount must be an integer, this value must be rounded down to 502 or up to 503. + // ii. + // If the right order were filled via `Exchange.fillOrder` the respective fill amounts would be [1004, 502] or [1006, 503]. + // It follows that we cannot trigger a sale of 1005 units of the right maker's asset through `Exchange.fillOrder`. + // iii. + // For an optimal match, the algorithm must choose either [1005, 502] or [1005, 503] as fill amounts for the right order. + // The algorithm favors the right maker when the exchange rate must be rounded, so the final fill for the right order is [1005, 503]. + // iv. + // The right maker fee differs from the right taker fee because their exchange rate differs. + // The right maker always receives the better exchange and fee price. + amountSoldByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(1005), 0), + amountBoughtByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(503), 0), + feePaidByRightMaker: Web3Wrapper.toBaseUnitAmount(new BigNumber('47.2718720602069614'), 16), // 47.27% // Taker - amountReceivedByTaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(8), 0), + amountReceivedByTaker: Web3Wrapper.toBaseUnitAmount(new BigNumber(497), 0), feePaidByTakerLeft: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% - feePaidByTakerRight: Web3Wrapper.toBaseUnitAmount(new BigNumber(100), 16), // 100% + feePaidByTakerRight: Web3Wrapper.toBaseUnitAmount(new BigNumber('47.3189087488240827'), 16), // 47.31% }; // Match signedOrderLeft with signedOrderRight await matchOrderTester.matchOrdersAndAssertEffectsAsync( -- cgit