Closed Brechtpd closed 4 years ago
Let's discuss here what to put in our next small protocol release. I think the general idea should be to minimize changes because we don't want to risk changing too many things. Circuit changes I think should be kept to the absolute minimum, while smart contracts can be changed a bit more as those are much more flexible.
Changes
- Increase number of accounts in Merkle tree to either
2**24
(16,777,216 accounts) or2**28
(268,435,456 accounts).2**24
needs 3 bytes/account,2**28
needs 3.5 bytes/account.
[Steve] 2**24
is enough.
Combine
commitBlock
+verifyBlocks
intosubmitBlocks
, allowing multiple blocks to be submitted at once (only the latest block is stored onchain, batch verification is used for verifying the blocks immediately). Because we can now prove even big blocks quite fast there is now much less of a reason for separate steps.
- Multiple blocks (of different types) can be committed which saves gas (only the latest state needs to be stored onchain).
- Blocks can't be reverted any more which simplifies things quite a bit. The state is always immediately finalized after
submitBlocks
.- Withdrawals can be done immediately as well so the data doesn't have to be stored onchain any more unless the transfer is unsuccessful. This would lower the costs for withdrawals as well in most cases as most withdrawal transfers won't fail. We can completely remove the need for
distributeWithdrawals
by making the amount withdrawable easily accessible onchain by using a simple map:amountWithdrawalbe[address][token]
. This makes it very easy for people/UIs to withdraw funds themselves without counting on the operator in the very unlikely scenario the withdrawal transfer (done immediately when the block is submitted onchain) fails.- Some quick calculations to see how this effects our throughput (best case scenario). As you can see even quite small blocks aren't too far from the best case with the biggest block sizes, so maybe for our next trusted setup we can do just up to 512 trades/block (or even 256 trades/block).
4096 trades/block: (100000 + 160000 + (4096*20*16 + 40000) * 7) / (4096*7 ) = 339 gas/trade 2048 trades/block: (100000 + 160000 + (2048*20*16 + 40000) * 14) / (2048*14 ) = 348 gas/trade 1024 trades/block: (100000 + 160000 + (1024*20*16 + 40000) * 27) / (1024*27 ) = 368 gas/trade 512 trades/block: (100000 + 160000 + ( 512*20*16 + 40000) * 47) / ( 512*47 ) = 409 gas/trade 256 trades/block: (100000 + 160000 + ( 256*20*16 + 40000) * 80) / ( 256*80 ) = 489 gas/trade 128 trades/block: (100000 + 160000 + ( 128*20*16 + 40000) * 120) / ( 128*120) = 649 gas/trade
- Conditional transfers
- Agents functionality: allowing contracts to do things for users etc… for all kinds of composability features. Completely onchain (no impact on circuits at all) and only needs limited changes in the protocol contracts. Any actual functionality using this can be done once needed.
Maybe Include
- Allow unlimited orders/account (but still the same limited number of active orders). Needs some changes to the trading history logic, but that should be small. Currently more than
2**20
orders per token is possible so not that important I think.
[Steve] 2**20
is far from enough. Actually our MarketMaking account already uses about 100 thousands orderID in only one week. Especially for ETH, USDT or DAI, they will be used as base trading token. So I suggest that we increase it to at least 2**24
.
- Allow dummy orders that don't trade anything. The current workaround for this I think is actually fine. Only when the necessary changes in the circuit are very easy.
- Split data necessary onchain from the DA data so we don't have to worry about copying all this data around in our smart contracts (which costs some gas). Only when the necessary changes in the circuit are very easy. This could also be solved on the smart contract level, which may be simpler.
Don't Include
- Permission bitmap or something that can limit certain functionality in some cases. The main reasons is that this would change the circuits quite a bit and can create edge cases (what with conditional transfers/fast withdrawals or any other onchain composability that depends on transfers that the user may or may not disable on the circuit level?). So at least for now I wouldn't build this into the protocol as this can also be achieved externally.
Please add any suggestions here for things you want to see changed and let me know if you agree with the current changes.
I think 2**24
(16,777,216 accounts) should be good enough.
Removing the ability to revert block will be a huge gain in simplicity and efficiency. @hosschao, the relayer should now be more careful before submitting blocks.
What exactly does it cost to support *unlimited* order id, is it equivalent to 2^64 or 2^128? I agree with Steve that 2^20 is not good enough for market makers. I'd propose 2^32 or 2^64 if the unlimited* support cost significantly more. The number of active orders can stay the same.
Is it possible to use the same trading circuits for transfers? The main benefit is that we can put them into one block. If this is feasible, we don't have to distinguish transfers from trading; thus we don't have to implement permission bitmap at all.
What exactly does it cost to support unlimited* order id, is it equivalent to 2^64 or 2^128? I agree with Steve that 2^20 is not good enough for market makers. I'd propose 2^32 or 2^64 if the unlimited support cost significantly more. The number of active orders can stay the same.
The cost is practically nothing. The reason I didn't do this before is because I didn't think it was necessary and i only thought about doing this pretty late and I didn't want to change the circuits any more for that (as there is a small change in behaviour, see below). It would be 2^254 (or something close to that).
The reason I didn't think this was really necessary is because there are a lot of tricks you can use to reuse trading slots. Obviously slots used by orders that are not filled at all can easily be reused without increasing the orderID as the trading history is still 0. But even if the trading history slot is non-zero you can still reuse slots used by other orders simply by changing the amountS/amountB of the new order. For example if there was a sell order of 1ETH/10LRC that was completely filled (trading history slot equals 1ETH), you can reuse the slot with the same orderID for another 1ETH/10LRC order simply by changing it to a 2ETH/20LRC order (which can only be filled for 1ETH). This is a simple example, but this would work for all orders. This allows reusing slots many, many times even without having to increase the orderID at all. Obviously we can't let users do this because it would be very confusing, but for automated trading it could be an acceptable solution.
2**20 is far from enough. Actually our MarketMaking account already uses about 100 thousands orderID in only one week.
@letsgoustc This kind of surprises me as the total number of transactions is currently only 80,000, unless you always simply increase the orderID even if not really necessary (e.g. even if the previous order with that orderID wasn't filled at all, so even without some of the tricks explained above).
The idea is instead of storing the complete orderID in the data availability data, only orderID % totalNumActiveOrders is stored + 1 bit if the slot is being overwritten or not. The only extra limitation this imposes is that you can only overwrite a slot in the trading tree if orderID == tradingHistory.orderID + totalNumActiveOrders
(with the current method orderID == tradingHistory.orderID + N * totalNumActiveOrders
is posible with N any number (limited by 2^20
orderIDs of course)). Would that be a problem? Orders that aren't filled aren't stored in the tree so in that case you are forced to reuse the orderID of the order that wasn't filled.
Is it possible to use the same trading circuits for transfers? The main benefit is that we can put them into one block. If this is feasible, we don't have to distinguish transfers from trading; thus we don't have to implement permission bitmap at all.
Trades and transfers are currently very different and this would need a lot of work, changing a lot of circuit code. Transfers also only use 50% the number of constraints and this would make both more expensive. I think changing this would be too big to do for this release. I also don't quite follow how this would remove the need to do permission bitmaps as it doesn't solve the problem that aims to solve (stop transfers from happening by some users).
What exactly does it cost to support unlimited* order id, is it equivalent to 2^64 or 2^128? I agree with Steve that 2^20 is not good enough for market makers. I'd propose 2^32 or 2^64 if the unlimited support cost significantly more. The number of active orders can stay the same.
The cost is practically nothing. The reason I didn't do this before is because I didn't think it was necessary and i only thought about doing this pretty late and I didn't want to change the circuits any more for that (as there is a small change in behaviour, see below). It would be 2^254 (or something close to that).
Then I think we should support the unlimited order id.
The reason I didn't think this was really necessary is because there are a lot of tricks you can use to reuse trading slots. Obviously slots used by orders that are not filled at all can easily be reused without increasing the orderID as the trading history is still 0. But even if the trading history slot is non-zero you can still reuse slots used by other orders simply by changing the amountS/amountB of the new order. For example if there was a sell order of 1ETH/10LRC that was completely filled (trading history slot equals 1ETH), you can reuse the slot with the same orderID for another 1ETH/10LRC order simply by changing it to a 2ETH/20LRC order (which can only be filled for 1ETH). This is a simple example, but this would work for all orders. This allows reusing slots many, many times even without having to increase the orderID at all. Obviously we can't let users do this because it would be very confusing, but for automated trading it could be an acceptable solution.
2**20 is far from enough. Actually our MarketMaking account already uses about 100 thousands orderID in only one week.
@letsgoustc This kind of surprises me as the total number of transactions is currently only 80,000, unless you always simply increase the orderID even if not really necessary (e.g. even if the previous order with that orderID wasn't filled at all, so even without some of the tricks explained above).
The idea is instead of storing the complete orderID in the data availability data, only orderID % totalNumActiveOrders is stored + 1 bit if the slot is being overwritten or not. The only extra limitation this imposes is that you can only overwrite a slot in the trading tree if
orderID == tradingHistory.orderID + totalNumActiveOrders
(with the current methodorderID == tradingHistory.orderID + N * totalNumActiveOrders
is posible with N any number (limited by2^20
orderIDs of course)). Would that be a problem? Orders that aren't filled aren't stored in the tree so in that case you are forced to reuse the orderID of the order that wasn't filled.Is it possible to use the same trading circuits for transfers? The main benefit is that we can put them into one block. If this is feasible, we don't have to distinguish transfers from trading; thus we don't have to implement permission bitmap at all.
Trades and transfers are currently very different and this would need a lot of work, changing a lot of circuit code. Transfers also only use 50% the number of constraints and this would make both more expensive. I think changing this would be too big to do for this release. I also don't quite follow how this would remove the need to do permission bitmaps as it doesn't solve the problem that aims to solve (stop transfers from happening by some users).
I see. I'm fine with they are two circuits. My concern is that account owners will no longer willing to share the trading key with a MM as the MM now can transfer all money away using the new transfer function.
One of the things I've been thinking about is to allow order creation onchain in a similar way that we now have conditional transfers that are approved onchain. This will allow any EOA/smart contract to directly create orders onchain which could be important for integrations where e.g. only a smart contract can sign off on orders. Like conditional transfers this will be more expensive to do, but in some cases this may be useful, I'm not sure yet.
I’m not sure if this will be helpful if strict order matching is not done onchain.
在 2020年4月20日,05:00,Brecht Devos notifications@github.com 写道:
One of the things I've been thinking about is to allow order creation onchain in a similar way that we now have conditional transfers that are approved onchain. This will allow any EOA/smart contract to directly create orders onchain. Like conditional transfers this will be more expensive to do, but in some cases this may be useful, I'm not sure yet.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.
What do you mean with strict order matching? The order matching would be completely the same between onchain and offchain orders (or at least very close to it for things like time constraints). Basically it replaces the need for the EdDSA signature, the rest should be basically the same.
Someone would submit the amountS
/amountB
pair (+ some extra data like the orderID, the fee amount and time constraints) and these would be used to validate the fill amounts passed into the onchain data-availability data. Everything (except the missing EdDSA signature) should remain the same. Well, at least that's the idea, but I think it should be possible.
@dong77 Some stats for bigger Merkle trees.
Constraints: V3.0 (accounts: 2^20, tokens: 2^8): 64,500 constraints/trade V3.5 (accounts: 2^24, tokens: 2^8): 67,000 constraints/trade (+4% compared to V3.0) V3.5 (accounts: 2^24, tokens: 2^10): 71,000 constraints/trade (+10% compared to V3.0) V3.5 (accounts: 2^24, tokens: 2^12): 75,000 constraints/trade (+16% compared to V3.0) V3.5 (accounts: 2^24, tokens: 2^16): 83,000 constraints/trade (+28% compared to V3.0)
DA: V3.0 (accounts: 2^20, tokens: 2^8): 20 bytes/trade V3.5 (accounts: 2^24, tokens: 2^8): 20 bytes/trade (+0% compared to V3.0, because of orderID opt) V3.5 (accounts: 2^24, tokens: 2^10): 21 bytes/trade (+5% compared to V3.0) V3.5 (accounts: 2^24, tokens: 2^12): 21 bytes/trade (+5% compared to V3.0) V3.5 (accounts: 2^24, tokens: 2^16): 22 bytes/trade (+10% compared to V3.0)
I prefer to go with accounts: 2^24, tokens: 2^10
What do you mean with strict order matching? The order matching would be completely the same between onchain and offchain orders (or at least very close to it for things like time constraints). Basically it replaces the need for the EdDSA signature, the rest should be basically the same.
Someone would submit the
amountS
/amountB
pair (+ some extra data like the orderID, the fee amount and time constraints) and these would be used to validate the fill amounts passed into the onchain data-availability data. Everything (except the missing EdDSA signature) should remain the same. Well, at least that's the idea, but I think it should be possible.
I understand what you are saying. By "strict order matching", I mean a fully onchain match-engine will have to respect which order to match first, but with our relayer being a centralized piece of infrastructure, an on-chain order cannot assume it will be filled even if some well-known price oracle indicates the order shall have been filled. Therefore, the contract who posts such an on-chain order will have to find a way to check if the order has been filled... which may be hard.
Current each ERC20 token registered has a unique ID. I'm thinking another design, let's say we can support two IDepositContracts for LRC, one is static and does nothing, the other one is an interesting earning contract that pays some interests. Maybe when we register tokens, we assign two different token ids for LRC:
registerToken("lrctoken.eth", "static_lrc_deposit_contract") // gives token id=1
registerToken("lrctoken.eth", "interest_earning_lrc_deposit_contract") // gives token id=2.
So basically tokenId = token_address + token_deposit_contract address.
People have different levels of risk tolerance. If LRC can only have 1 ID, then some users will be happy with the DepositContract implement, and others will be unhappy and they will probably leave. Enableing multiple IDs for the same token will likely to keep them all.
Going forward, we may want to make sure to provide static deposit contract that does nothing, for all tokens. So people don't trust us will continue using the DEX; then we can offer another set of DeFI integrated deposit contracts.
The above idea will certainly create different LRC markets such as LRC1/USD, LRC2/USD, etc.
I've been thinking of using a bytes array for tokens because this could potentially allow even future tokens that may need more data than a single address (like a security token with multiple tranches that should be traded separately). Because we don't use the token address inside the exchange any more (as far as I know, not 100% sure about this, ETH being the zero address is probably the only exception) the token data could be pretty much any data that the deposit contract can interpret itself.
Seems like this is general enough to also allow doing what you describe. Though if the deposit contract can't be made secure enough for all users than I'd say it probably shouldn't be used for any users at all. Though this is probably easier said than done.
I understand what you are saying. By "strict order matching", I mean a fully onchain match-engine will have to respect which order to match first, but with our relayer being a centralized piece of infrastructure, an on-chain order cannot assume it will be filled even if some well-known price oracle indicates the order shall have been filled. Therefore, the contract who posts such an on-chain order will have to find a way to check if the order has been filled... which may be hard.
I'm assuming a use case like selling our protocol fees using an auction. The funds are deposited, the trade is enabled at some price and the after some time the contract withdraws whatever the new account balances are. And this could continue as long as needed. So onchain the contract just detects what happened by whatever it got back from the exchange in the withdrawals. Though most likely it's actual people that are watching what is happening and decide what will happen onchain with voting/multi-sig depending on the kind of contract and need.
I've been thinking of using a bytes array for tokens because this could potentially allow even future tokens that may need more data than a single address (like a security token with multiple tranches that should be traded separately). Because we don't use the token address inside the exchange any more (as far as I know, not 100% sure about this, ETH being the zero address is probably the only exception) the token data could be pretty much any data that the deposit contract can interpret itself.
Seems like this is general enough to also allow doing what you describe. Though if the deposit contract can't be made secure enough for all users than I'd say it probably shouldn't be used for any users at all. Though this is probably easier said than done.
After we use the new ABI encoder, is it possible to create a struct like:
struct TokenAttirubutes {
mapping (string =>bytes) attirbutes
}
and use this struct directly?
I understand what you are saying. By "strict order matching", I mean a fully onchain match-engine will have to respect which order to match first, but with our relayer being a centralized piece of infrastructure, an on-chain order cannot assume it will be filled even if some well-known price oracle indicates the order shall have been filled. Therefore, the contract who posts such an on-chain order will have to find a way to check if the order has been filled... which may be hard.
I'm assuming a use case like selling our protocol fees using an auction. The funds are deposited, the trade is enabled at some price and the after some time the contract withdraws whatever the new account balances are. And this could continue as long as needed. So onchain the contract just detects what happened by whatever it got back from the exchange in the withdrawals. Though most likely it's actual people that are watching what is happening and decide what will happen onchain with voting/multi-sig depending on the kind of contract and need.
From the implementation point of view, how can the relayer verify on onchain-order? We may have to assign an 'onchainOrderId' so during settlement, we check the ID is valid and not used.
I've been thinking of using a bytes array for tokens because this could potentially allow even future tokens that may need more data than a single address (like a security token with multiple tranches that should be traded separately). Because we don't use the token address inside the exchange any more (as far as I know, not 100% sure about this, ETH being the zero address is probably the only exception) the token data could be pretty much any data that the deposit contract can interpret itself.
Seems like this is general enough to also allow doing what you describe. Though if the deposit contract can't be made secure enough for all users than I'd say it probably shouldn't be used for any users at all. Though this is probably easier said than done.
The other way to do it is to change our ABI to reference tokens not by addresses, but by token ids. For example:
function deposit(
address from,
address to,
address tokenAddress,
uint96 amount
)
external
payable;
will be changed to
function deposit(
address from,
address to,
uint16 tokenId,
uint96 amount
)
external
payable;
inside our protocol, we have a mapping from token ID to its ERC20 address and deposit address.
The deposit address can even provide an isTokenSupported(address token) returns bool;
function. And it will be called inside the exchange's registerToken(address token, address depositContract)
function.
From the implementation point of view, how can the relayer verify on onchain-order? We may have to assign an 'onchainOrderId' so during settlement, we check the ID is valid and not used.
I think it should be pretty much the same as an offchain order. The onchain order will contain some orderID and that will be used for the settlement. I think basically all order data that's in the order offchain will simply be stored onchain in some way. The OCDA will be used to verify if the order was settled correctly. So if the offchain data doesn't allow settlement because e.g. the orderID points to a fully filled order than the order can't be filled, the same as with offchain orders.
The other way to do it is to change our ABI to reference tokens not by addresses, but by token ids. For example:
function deposit( address from, address to, address tokenAddress, uint96 amount ) external payable;
will be changed to
function deposit( address from, address to, uint16 tokenId, uint96 amount ) external payable;
inside our protocol, we have a mapping from token ID to its ERC20 address and deposit address.
The deposit address can even provide an
isTokenSupported(address token) returns bool;
function. And it will be called inside the exchange'sregisterToken(address token, address depositContract)
function.
This seems to be a nice solution as well! Not sure yet what the pros and cons are between the two different methods.
Please also see the following issues related to 3.5:
Implemented in #1105
Changes
Increased the number of accounts in the Merkle tree to
2**24
(16,777,216 accounts).2**24
needs 3 bytes/account.Increased the number of tokens in the Merkle tree to
2**10
(1024 tokens).Combine
commitBlock
+verifyBlocks
intosubmitBlocks
, allowing multiple blocks to be submitted at once (only the latest block is stored onchain, batch verification is used for verifying the blocks immediately). Because we can now prove even big blocks quite fast there is now much less of a reason for separate steps.submitBlocks
.distributeWithdrawals
by making the amount withdrawable easily accessible onchain by using a simple map:amountWithdrawalbe[address][token]
. This makes it very easy for people/UIs to withdraw funds themselves without counting on the operator in the very unlikely scenario the withdrawal transfer (done immediately when the block is submitted onchain) fails.withdrawBlockFee
.Conditional transfers
Agents functionality: allowing contracts to do things for users etc… for all kinds of composability features. Completely onchain (no impact on circuits at all) and only needs limited changes in the protocol contracts. Any actual functionality using this can be done once needed.
Allow unlimited orders/account (but still the same limited number of active orders). Needs some changes to the trading history logic, but that should be small. Currently more than
2**20
orders per token is possible so not that important I think.Allow dummy orders that don't trade anything. The current workaround for this I think is actually fine. Only when the necessary changes in the circuit are very easy.
Remove the dedicated order cancellation circuit. There is no need to have a circuit dedicated for order cancellation as there are already a lot of different ways an order can be canceled.
Dedicated deposit contract to support using locked funds of users in some way (e.g. store into a DeFi dapp to earn interest). Also allows supporting more token standards than ERC20. The address of the token can be any data the exchange wants to use for the token and is not required to be the address of the token itself. The only thing the exchange contract needs to know if the token is used for ETH or not (because the necessary msg.value needs to be sent to the deposit contract). In the deposit contract, the token "address" can then be used to lookup the actual token address to do the transfer. This way the same token can have multiple deposit behaviors while still mapping to the same token. However, in the most common cases, the token address will actually contain the address of the token. This way we don't overcomplicate the interfaces or integrations for the (relatively small) chance that this may be useful, but it's still possible.
Removed labels
Updated to solidity 0.6.6
Don't Include
Permission bitmap or something that can limit certain functionality in some cases. The main reasons are that this would change the circuits quite a bit and can create edge cases (what with conditional transfers/fast withdrawals or any other onchain composability that depends on transfers that the user may or may not disable on the circuit level?). So at least for now, I wouldn't build this into the protocol as this can also be achieved externally.
Split data necessary onchain from the DA data so we don't have to worry about copying all this data around in our smart contracts (which costs some gas). Only when the necessary changes in the circuit are very easy. This could also be solved on the smart contract level, which may be simpler. Conclusion: Not necessary. When making sure memory-to-memory copies are never done (solidity can add these when you're not expecting them) the overhead is only 1%-1.5% for each external contract call on the data. This also means we can move out any decompression the data needs to an operator contract as this has the same cost as doing it inside the exchange contract. The benefit is that parsing the data that comes into the exchange contract always has the same format, which is very helpful for apps reading this data (like Dune).
Circuit changes
https://github.com/Loopring/protocol3-circuits/pull/36