RE: The first 5 days of the EOS token sale will be unfair. Here's how to fix it.

[dan]

Unfortunately ethereum cannot implement this algorithm due to gas constraints and lack of sorted database.

Comments

[arhag]

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 the bid_id of the new bid, and the eth_filled value 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 the eth_amount and time (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 the bid_id and 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 the bid_idthrough an indirect process which involves first using the bid period sequence number and the bid_id to 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 ascending time) 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, and last_processed_bid. During stage 1, each bid and bid update would also be tracking the total ETH collected for that bid period in eth_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 starting bid_id (which is what last_processed_bid is set to), and it also resets eth_accumulator and eth_to_keep to 0 and sets status to 1.

Then, the crowdfund manager uses another special transaction (only valid if status is either 1 or 2) which supplies a array of bid_ids which causes the smart contract to do the following. It uses last_processed_bid to get the limit_price and time of the corresponding bid, and then it iterates through the input array of bid_ids in order ensuring that limit_price and time of each processed bid follows the order requirements. As it processes each bid it will update last_processed_bid to bid_id of the processed bid and it will add their eth_amount to eth_accumulator. It will also add the eth_amount of the bid to eth_to_keep and set the bid's eth_filled value to the appropriate amount (usually equal to eth_amount but it could be less if the bid was only partially filled) if the bid's limit_price is large enough (based on EOS to distribute for that bid period and the accumulated eth_to_keep); once the limit_price threshold has been passed, it will set status to 2 so that it can use a shortcut and avoid calculating the price to compare with limit_price for 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 if eth_accumulator == eth_collected. If so, that will mark the transition to stage 3a by setting status to 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 the eth_filled amount and can retrieve the remaining eth_amount - eth_filled amount 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.

[biophil]

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.

[alexpmorris]

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

wow that's great I was just looking more into how a buy limit and even cancels could be implemented and it seems you guys are already in the process of adding it in a recent pull request! from what I've been reading, I was also coming to the conclusion that "mapping" and "memory" were the best "tricks" to help get there... buyWithLimit pullreq .. https://github.com/EOSIO/eos-token-sale/commit/e9280da6a34bf571e0122c4c7ad47c5c599490e6

Actually, just wrote a post about it too: "EOS Token Sale Smart Contract May Offer BUY LIMITS after all!"

[alexpmorris]

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".

For added utility, we will make our sorting function generic: we will sort pairs instead of integers. Thus, for examples, [30, 1, 90, 2, 70, 3, 50, 4] would become [ 30, 1, 50, 4, 70, 3, 90, 2 ]. Using this function, one can sort a list containing any kind of object simply by making an array of pairs where the first number is the key to sort by and the second number is a pointer to the object in parent memory or storage.

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.

[everythink]

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?

[celsius100]

Well, there ya go. Thanks for the quick answer. It would have been a great solution.