You are viewing a single comment's thread from:
RE: The first 5 days of the EOS token sale will be unfair. Here's how to fix it.
Unfortunately ethereum cannot implement this algorithm due to gas constraints and lack of sorted database.
Unfortunately ethereum cannot implement this algorithm due to gas constraints and lack of sorted database.
What about the following implementation? Keep in mind, I haven't spent a lot of time fully thinking through everything and there could be some errors or other problems (dealing with Ethereum performance limitations making this too costly) with this design.
Each bid identified uniquely by the address of sender and bid period sequence number (first 5 day period counts as bid period sequence 0, and the remaining days just increment that sequence number) has the following state associated with it:
bid_id,eth_amount,time,limit_price,eth_filled. For each bid period, a bid ID sequence counter is maintained. When creating a new bid, that sequence number is incremented and used as thebid_idof the new bid, and theeth_filledvalue is set to 0. A user can add or remove ether from their bid before the end of that bid period; such modifications only change theeth_amountandtime(which is always updated to the current time when the bid is changed by the owner of the bid) but not any of the remaining fields. When creating a new bid, the smart contract also constructs an index: state consisting of the address of the bidder that is identified uniquely by thebid_idand bid period sequence number. The idea of that index is that the smart contract can lookup the state associated with a user's bid using the bid period sequence number and thebid_idthrough an indirect process which involves first using the bid period sequence number and thebid_idto get the address associated with that bid, and then using the address and the bid period sequence number to get access to the state associated with the bid.When the bid period ends, it enters a new stage (stage 2) that will last for at most a day. During the stage all the bids are locked to their owners (they cannot add or remove ETH from them). After stage 2 finishes, the smart contract can either enter stage 3a or stage 3b depending on what happens in stage 2. If a special address (controlled by the managers of this crowdfund) is able to provide a complete proof (I will explain this shortly) to the smart contract that all bids were processed correctly in order of descending
limit_price(and tie breakers done by ascendingtime) before the end of that 1 day deadline, then the smart contract enters stage 3a in which the owners of the bids that were "filled" can claim their appropriate amount of EOS tokens, while those whose bids were not "filled" can take back their ETH. If the crowdfund manager is not able to complete the proof by the deadline, the smart contract automatically enters stage 3b which basically allows all the bidders in that bid period to take back their ETH.So how does this proof work? The crowdfund manager is authorized (during stage 2 of a particular bid period) to send certain transactions that will allow the smart contract to iterate through the bids of that bid period in a certain order. First, there is some state associated with each bid period. This state includes
status,eth_accumulator,eth_collected,eth_to_keep, andlast_processed_bid. During stage 1, each bid and bid update would also be tracking the total ETH collected for that bid period ineth_collected; the other fields would all be initialized to 0. Then in stage 2, the crowdfund manager can initiate the proof process with a special transaction that allows them to set the startingbid_id(which is whatlast_processed_bidis set to), and it also resetseth_accumulatorandeth_to_keepto 0 and setsstatusto 1.Then, the crowdfund manager uses another special transaction (only valid if
statusis either 1 or 2) which supplies a array ofbid_ids which causes the smart contract to do the following. It useslast_processed_bidto get thelimit_priceandtimeof the corresponding bid, and then it iterates through the input array ofbid_ids in order ensuring thatlimit_priceandtimeof each processed bid follows the order requirements. As it processes each bid it will updatelast_processed_bidtobid_idof the processed bid and it will add theireth_amounttoeth_accumulator. It will also add theeth_amountof the bid toeth_to_keepand set the bid'seth_filledvalue to the appropriate amount (usually equal toeth_amountbut it could be less if the bid was only partially filled) if the bid'slimit_priceis large enough (based on EOS to distribute for that bid period and the accumulatedeth_to_keep); once thelimit_pricethreshold has been passed, it will setstatusto 2 so that it can use a shortcut and avoid calculating the price to compare withlimit_pricefor the remaining bids to be processed since it knows that none of them will be filled. Finally, at the end of the transaction, the smart contract will check to see ifeth_accumulator == eth_collected. If so, that will mark the transition to stage 3a by settingstatusto 3.In stage 3a, any bid that was fully "filled" (meaning
eth_filled == eth_amount) can claim the appropriate amount of EOS. But if they were not filled, then the owner of that bid can simply reclaim their ETH from the bid. At most one of the bids in a bid period may be partially filled (eth_filled < eth_amount); for this bid, the owner can claim the appropriate amount of EOS based on theeth_filledamount and can retrieve the remainingeth_amount - eth_filledamount of ETH back.So, the idea is to have the expensive sorting be done off-chain by the crowdfund manager, and then to have them supply that sequence via a special operation only they are allowed to use in stage 2. The smart contract will ensure that the crowdfund manager cannot cheat by using an invalid order or leaving off certain bids. The only thing the crowdfund manager can do is refuse to complete the proof in time (within a day), which would be as if that bid period never happened (the smart contract could automatically extend the number of bid periods to try again and ensure 360 1-day bid periods do in fact occur). Also, this design provides a lot of flexibility to the crowdfund manager in providing the bid sequence proof. First, it allows them to break up the proof into multiple transactions so that there isn't an issue of a single transaction which provides the entire sequence of bids for the bid period being too computationally demanding to be accepted by the Ethereum network. Second, it is forgiving. If for some reason the crowdfund manager messes up by leaving off a bid (although I don't see why this should happen in the first place since they would be using bots to do it), they aren't forced to basically allow the entire bid period to become void; they can simply use the special transaction to re-initiate the proof process and start the proof over again.
I was afraid of that, and just before you commented I had updated my post to mention that possible problem.
I guess to implement it you'd need to do a literal descending price auction a la Gnosis, which I wouldn't be so quick to support.
Thanks for the quick answer.
hey @biophil, just noticed this on github and posted about it in the new EOS slack. thought you may also very much appreciate hearing about it! :D
Actually, just wrote a post about it too: "EOS Token Sale Smart Contract May Offer BUY LIMITS after all!"
This example by Vitalik Buterin is from 2014, but he does show an implementation of a generic quicksort algorithm that can sort object pairs. Now, I'm not sure of the "gas constraints" involved, but with a sorted object pair it should be relatively straightforward to sort by "limit price", "database ID".
Link: Advanced Contract Programming Example: SchellingCoin
Link: GitHub SchellingCoin implementation from Ethereum Repo
I admit I'm not well-versed in EC20 contracts or serpent/solidity, but technically, shouldn't we also be able to see all the current bidders and make an outside calculation of what the expected price would be before the window closes? If so, even better if someone could "cancel their order" before the window closes if they are displeased with the expected closing price.
Maybe for the first 5 days stage we can use regular servers, I mean without smart contract? We can launch a transparent site (ethereum blockchain explorer which is filtering one particular ETH address), so everyone could see all the bids. Then site would filter these bids as it shown in biophil's post. After 5 days stage is over, the smart contract starts.
BTW, if crowdsale will last for a year, when will EOS network itself start? After that year of eairlier?
Well, there ya go. Thanks for the quick answer. It would have been a great solution.