I have some improvements to the previous post.
tl;dr: This post describes how to implement a decentralized BTC/BitBTC exchange (with bid and ask orders) on the BitShares blockchain where the BTC sellers are motivated to settle their debts within T hours (T = 30 is a good choice) or else they forfeit a bond to their BitBTC-selling counterparty (who also gets back the BitBTC they paid for the failed trade) that is worth at most X% (obviously less than 100%) of the amount that the counterparty paid for the trade. All of this functions if we assume that at least some quorum (a threshold of at least a majority is preferred) of the active delegates do their job (and do it honestly). The BitBTC seller is exposed to the risk that a quorum of delegates (a quorum higher than the threshold) collude to defraud them out of the matched BitBTC they offered. The BTC seller is exposed to the risk that the quorum of delegates collude to defraud them out of the matched BTC offered as well as the X% BitBTC bond. Finally, there is no reason this has to be limited to BitBTC. The same mechanism could function for a BTC/BitUSD market, although because of the volatility risk it may be necessary to change the value of X to ensure that it is unlikely for the price of BTC (in BitUSD) to grow faster than X% in T hours (nor X'% in T' hours).
Before I had said that only the ask orders would exist on the blockchain. The bid orders would be immediate or cancel only. But I think it is fine if there is another type of regular bid order that sits in the order book. Like the other bid order, this regular bid order specifies the unique number of Bitcoin addresses in the ask orders that it is allowed to match against, the signed void transaction (which I will now call a withdraw transaction) with the nLockTime roughly T hours in the future, and a BitBTC bond that is X% of the quantity of BitBTC requested in the bid order. However, in this case I think T should be closer to 30 hours and perhaps X should still be 10% or maybe it should be more to compensate for the larger amount of time that the ask's BitBTC could be locked up (these are parameters that can vary with the specific market). The immediate or cancel bid orders will have their own time T' < T and percentage X' <= X (but I recommend that X'/T' >= X/T). These regular bid orders would first match with any ask orders they overlap with at the moment they are submitted to create the same types of positions ("immediate positions") as the IOC (Immediate or Cancel) orders (meaning they would use the T' and X' parameters) then any remaining amount would sit in the order book and if it later gets matched will create a "latent position" and will instead use parameters T and X. The reason for the larger T > T' is because we can expect the bidder to be online to submit the Bitcoin transaction immediately after the IOC bid is submitted, but by the time a sitting bid order is matched, the bidder may have already gone offline. Therefore T should be large enough to give the bidder enough time to check if the bid has been matched and settle the payments with a Bitcoin transaction. If the bid is partially matched 24 hours after first submitting the bid, the bidder has the remaining 6 hours to cancel remaining bid orders, settle his obligations by making the necessary payments through a Bitcoin transaction, and then resubmit the bids for the remaining quantity (I discuss a better way of doing this using "renew transaction" below).
A bidder (someone who has BTC and wants BitBTC) first needs to submit a "BTC deposit" transaction on the BitShares blockchain. A "BTC deposit" transaction requires a pointer to a confirmed BTC balance on the Bitcoin blockchain, a signed "BTC withdraw" transaction (which is a signed Bitcoin transaction spending the BTC balance with some nLockTime Bitcoin block in the future and with an appropriate transaction fee included), and a positive integer N specifying the maximum number of unique Bitcoin addresses that bid orders paid through this balance can be matched against. Initially, the "BTC deposit" balance is inactive and can't be used to do anything (although it can be made void by the owner). For the "BTC deposit" balance to become active, it requires an "activate BTC deposit" transaction to be submitted to the blockchain which activates the "BTC deposit" balance and also initializes two mutable fields of the "BTC deposit" balance: a timestamp (called the "expiration time" of the "BTC deposit" balance) which estimates an upper bound on the time by which this balance will be forced to move; and a quantity (called the "BTC quantity" of the "BTC deposit" balance) which represents the amount of BTC held in the actual balance on the Bitcoin blockchain. The blockchain considers an "activate BTC deposit" transaction valid if it sets these two values and is signed by the necessary quorum of delegates (no one else can generate this transaction). The signature could either be done as a multisig or even better using a threshold signature where the public key of the threshold is already established in the block header (that is another discussion). Initially, the delegates set the timestamp to the estimated time the Bitcoin block specified by the nLockTime in "BTC withdraw" transaction will be generated (assuming 10 minute block intervals). The delegates are expected to produce the "activate BTC deposit" transaction for any "BTC deposit" transaction that is valid (meaning that it points to an actual confirmed unspent BTC balance on the blockchain that had not been submitted as a "BTC deposit" to the BitShares blockchain before, and the signed "BTC withdraw" transaction is valid).
A bid order for BitBTC in the BTC/BitBTC market specifies a limit price, a BitBTC quantity, the "BTC deposit" balance from which it will pay the BTC, and whether it is IOC or not. The bid order must also include some amount of BitBTC as part of bond for the order. If the bid order is IOC, then X'% of the quantity must be provided. A submitted bid order can only be IOC if the "expiration time" of the "BTC deposit" balance that the bid is associated with is less than T' hours in the future. If the bid order is not IOC, then X% of the quantity must be provided. Even if a submitted bid order is not IOC it is still required that the "expiration time" of the "BTC deposit" balance that the bid is associated with be less than T hour in the future. Also for any bid order submission to be accepted (regardless of whether IOC or not) into the blockchain, the outstanding BTC to be paid or being offered thus far for all positions and open bids (including the newly submitted pending bid) associated with the "BTC deposit" balance cannot exceed the "BTC quantity" of the "BTC deposit" balance. When bid orders are submitted a reverse index is maintained from the "BTC deposit" balance to the bid orders that are using them. When the bid order is IOC it will match against ask orders that existed prior to the block it is included in without paying any overlap fees up to the limit price (meaning it is a limit order), and anything that is not matched will then be cancelled and the corresponding BitBTC returned to the bidder. When the bid order is not IOC, it will match against ask orders that existed prior to and included in the block in which the bid order is included in with the standard overlap rules and the price set at the limit price, and anything that is not matched will sit at the limit price in the order book as a latent bid order. The positions formed from bids matching with asks immediately after submission of the bid are called "immediate positions". These positions take X'% of the BitBTC quantity matched from the bid and store it in escrow along with the quantity of BitBTC matched from the ask. The positions formed from asks matching with bids immediately after the submission of the ask are called "latent positions". These positions take X% of the BitBTC quantity matched from the bid and store it in escrow along with the quantity of BitBTC matched from the ask. Each of these positions is associated with a particular "BTC deposit" balance (the one of the bid that was matched to form the position) and an appropriate reverse index is maintained from the balance to these positions (along with the open bid orders as well). Since X >= X', some amount of the BitBTC bond provided with a non-IOC bid will be unnecessary assuming there are any "immediate positions" formed from that bid. The quantity of BitBTC matched into "immediate positions" times (X-X')% will be refunded back to the bidder immediately after submitting the bid. The remaining BitBTC bond will stay with the latent bid orders to cover the X% bond for matching.
When a Bitcoin transaction spending the balance pointed to by the "BTC deposit" transaction is confirmed in the Bitcoin blockchain, the delegates are expected to submit an appropriate multisig (or threshold sig) transaction to the BitShares blockchain that causes several possible things to occur. The delegates submit a "BTC balance moved" transaction which specifies the "BTC deposit" transaction it refers to and also specifies a renew flag, a BitShares block height, and a varint. Also, if the renew flag is set to true, the transaction also includes the new values for the "expiration time" and "BTC quantity" of the "BTC deposit" balance. The renew flag is a boolean which if true tells the blockchain to renew the balance (and thus keep the existing open bids associated with the "BTC deposit" balance) and if false tells the blockchain to cancel the balance (and thus cancel all existing open bids associated with the "BTC deposit" balance and return their BitBTC bonds back to the bidder). The varint encodes information specifying which BTC addresses (of the ones associated with the matched asks that the bidder has an obligation to eventually pay) were paid in full (according to the bidder's obligation as of the moment of the block specified by the block height) by the Bitcoin transaction. A list of BTC addresses of asks that were matched against the bids associated to a particular "BTC deposit" balance can be compiled at any time (any block) in a deterministic order (in lexicographical order of the BTC address for example). The varint encodes a bit array, where the block height specifies the block at which the ordered list of BTC addresses of the asks should be compiled for the given "BTC deposit" balance and the bit array specifies in the same order whether or not that address was paid the full amount that they were owed by the bidder's BTC transaction. The blockchain determines all of the BTC addresses the bidder needs to pay (and how much BTC the bidder needs to pay to each) as of the block specified by the block height and generates a ephemeral map between BTC addresses and BTC amounts to be paid. The blockchain then generates a new ephemeral map from the first by filtering out any of the BTC addresses that were not paid in full according to the bit array. The blockchain then determines all of the BTC addresses the bidder needs to pay (and how much BTC the bidder needs to pay to each) as of a block which is either the current block the "BTC balance moved" transaction is included in if the renew flag is false or the block in which the latest "renew balance" transaction (discussed below) associated with the "BTC deposit" balance was submitted if the renew flag is true, and generates a third ephemeral map between BTC addresses and BTC amounts to be paid. For each of the BTC addresses A in the third map, the blockchain takes the amount to be paid from the third map (AMOUNT_OWED BTC) and compares it to the amount to be paid for the corresponding address A in the second map (AMOUNT_PAID BTC), or sets AMOUNT_PAID to 0 if A does not exist in the second map. AMOUNT_PAID should never exceed AMOUNT_OWED, but it can be less. For each of the "immediate positions" and "latent positions" associated with the "BTC deposit" balance and address A (restricted only to the positions formed prior to the block that is 5 blocks prior to the block in which the latest "renew balance" transaction associated with the "BTC deposit" balance was included in, if renew flag is true, and no restriction if it is false), which have Y BitBTC held in escrow in the position, (AMOUNT_PAID/AMOUNT_OWED)*Y BitBTC is taken from the escrow of the position and sent to the bidder and the rest (if any) is sent to the ask side of the position.
An owner of a "BTC deposit" balance can submit a "renew balance" transaction on the "BTC deposit" balance which specifies everything a "BTC deposit" transaction does (pointer to BTC balance, signed "BTC withdraw" transaction, and a new value for N). If any existing "renew balance" transaction was associated to the "BTC deposit" balance, it is replaced by the new one. A "renew balance" transaction will not be submitted into a block if the block height of the block it is submitted into is not greater than 5 more than the block height of the block in which the "BTC deposit" transaction was submitted in. When a Bitcoin transaction spending the balance pointed to by the "BTC deposit" transaction is confirmed in the Bitcoin blockchain and the delegates are expected to create and submit the "BTC balance moved" transaction, they need to first check whether a "renew balance" transaction is associated with the "BTC deposit" balance. If so, they need ensure the following:
- The pointer in the "renew balance" transaction points to an output balance of the transaction that spent the BTC balance that was pointed to by the "BTC deposit" transaction.
- The accumulated quantity of BTC asked by all the open bid orders associated to this "BTC deposit" balance is less than or equal to the quantity of BTC held in the new output balance pointed to by the "renew balance" transaction.
- The signed "BTC withdraw" transaction in the "renew balance" transaction is valid (meaning it spends the new output balance, has the appropriate Bitcoin fee, and has the necessary signatures) and has an nLockTime that is at a Bitcoin block in the future that is estimated (based on 10 minute block intervals) to be produced prior to T hours in the future.
If all of the above are true, the delegates will create the "BTC balance moved" transaction with the renew flag set to true. If any of the above are false, the delegates will create the "BTC balance moved" transaction with the renew flag set to false. The delegates then come to a consensus on the block height to use in the "BTC balance moved" transaction, which is selected to be the block height of the block that is 5 blocks prior to the block that the aforementioned "renew balance" transaction exists in if the renew flag is set to true or the most recent block that enough of the delegates (enough to satisfy the multisig or threshold sig properties of the "BTC balance moved" transaction) can reach a consensus on (typically just the current head block at the time the transaction is being created) if the renew flag is set to false. The delegates then calculate the ordered list of (A, Y) where the A represents the BTC addresses that are owed BTC (and Y is the quantity of BTC they are owed) due to matching of the bids associated with the "BTC deposit" balance with asks as of the specified block height, where the order of the list is determined through lexicographical ordering of A. Each delegate can then map this list of tuples to a bit sequence (the bit array) by outputting a 1 bit if there exists an output balances in the Bitcoin transaction spending the BTC balance which can be claimed by address A and the quantity of BTC in that output balance is greater than or equal to Y, and outputting a 0 bit otherwise. Once this bit array has been calculated, they can each calculate the varint encoding the bit array (essentially representing the bit array as a large unsigned integer and then serializing it as a varint) and include that in the transaction. Finally, if the renew flag is set to true, the delegates also add a new "BTC quantity" field to the transaction which is set to the amount of BTC in the new output balance and also add a new "expiration time" field to the transaction which is set to the estimated time that the Bitcoin block specified by the nLockTime in new signed "BTC withdraw" transaction will be generated (assuming 10 minute block intervals). They then finalize the transaction, collectively sign (multisig or threshold) the transaction, and submit it into the BitShares blockchain.
If the bidder wants to guarantee (assuming delegates behave) that his obligations will be fully satisfied rather than partially satisfied (so that he doesn't lose any of his BitBTC bond), he needs to do a few things. First, the bidder must always submit the Bitcoin transaction satisfying his obligations well before the deadline (the time when the nLockTime of the submitted "BTC withdraw" transaction becomes active). Second, if the bidder does not intend to renew the "BTC deposit" balance, he must cancel all open bid orders associated with that "BTC deposit" balance prior to generating the Bitcoin transaction that satisfies his obligations. Third, if the bidder does intend to renew the "BTC deposit" balance, he must first submit the appropriate and valid "renew balance" transaction and have it confirmed in the BitShares blockchain before broadcasting the Bitcoin transaction that satisfies his obligations up to the point of 5 blocks prior to the block the latest "renew balance" transaction was included in. This means whenever the bidder wants to update his renew checkpoint, the bidder's client will calculate obligations as of the current block, generate and sign a valid Bitcoin transaction (called the "spending transaction") spending the BTC balance that satisfies the current obligations and sends the rest (minus necessary transaction fee) back to an address the bidder controls (called the "renewed balance"), calculate the pointer to this "renewed balance", generate and sign a valid (with necessary fees) Bitcoin transaction (called the "new withdraw transaction") spending the "renewed balance" back to an address the bidder controls, and generate, sign, and broadcast a new BitShares "renew transaction" on the "BTC deposit" balance that includes the new pointer, the "new withdraw transaction", and a potentially new value for N. Once the BitShares transaction is included in the blockchain, the client can verify whether the bidder's obligations as of the block 5 blocks prior to the block this "renew transaction" is included in is the same as the bidder's obligations at the beginning of this process (which will almost always be true as long as the "renew transaction" is included in the BitShares blockchain without abnormal delays). If it is not true, the client gives the bidder the option to try again with a new "renew transaction" or the bidder can instead choose to cancel his open bids to avoid this potential (but rare) problem. After confirming the previous corner case, the client then gives the bidder the option to broadcast the "spending transaction" to the Bitcoin blockchain. If the bidder agrees, then this will start off the process that eventually causes the delegates to generate the corresponding "BTC balance moved" transaction which should settle the bidder's obligations as of the block the renew checkpoint process was started but still leave any remaining and future (if more of the open bids get matched) obligations to be handled later (at most approximately T hours later) using the "renewed balance" instead.
One thing to keep in mind with the "renew transaction" is if the new value of N for the "BTC deposit" balance is smaller than the number of unique BTC addresses of the asks of the collective "immediate positions" and "latent positions" associated with the "BTC deposit" balance, the market will automatically cancel all open bids associated with the "BTC deposit" balance. Furthermore, as soon as a latent bid being matched with an ask causes the number of unique BTC addresses of asks of the collective positions associated with the "BTC deposit" balance to be equal to N, the market engine will cancel all open bids associated with the "BTC deposit" balance (even ones that would have otherwise been matched in that same block). And in the case of newly placed immediate or latent bid matching against multiple asks, the market engine will ensure that the bid order (and any other bid order operations associated with the "BTC deposit" balance that are in the same transaction) will cancel as soon as the number of unique BTC addresses of asks of the collective positions associated with the "BTC deposit" balance becomes equal to N (even if they would have otherwise matched). This is all to ensure that the bidder is never put into a situation where to fully satisfy all of their obligations they need to create a Bitcoin transaction that has more than (N+1) outputs.
It is clear why a Bitcoin transaction spending the BTC balance may not satisfy any of the bidder's obligations (it could simply be the "BTC withdraw" transaction being submitted when the nLockTime passes because the bidder didn't settle his debts in time) and regular operation should consist of BTC transactions that satisfy all of the bidder's obligations. But what would be the reason for partial satisfaction of the bidder's obligations. One situation I can think of is if there are a lot of matches of tiny quantity with different ask counterparties (meaning different BTC addresses). Now the N parameter specified should put an upper bound on this (so the Bitcoin transaction the bidder needs to create to satisfy all obligations doesn't get too big), but if all N consist of a few satoshi matches, the bidder is better off letting the 10% of the accumulated satoshi in BitBTC bonds go to the ask counterparties rather than wasting a Bitcoin transaction fee satisfying these obligations with a large Bitcoin transaction with N+1 outputs (assuming transaction fees scale with Bitcoin transaction size). However, if 1 of the N actually is a match for 0.01 BTC and the remaining (N-1) are for a few satoshis, then if the system were designed such that obligations had to be fully satisfied or else the bidder loses all of his BitBTC bonds (which is of course a simpler design than the above), the bidder would lose approximately 0.001 BitBTC in bonds unless he fully satisfied the obligations with a large Bitcoin transaction that had (N+1) outputs. However, while a regular transaction spending the balance back to the bidder might not take a fee more than 0.0001 BTC, the transaction with (N+1) outputs might be (assuming reference implementation of Bitcoin) ceil((125 + 34*N)/1000) * 0.0001 BTC. So with N = 330, the bidder might have to pay a transaction fee of 0.0012 BTC which would be worth more (even after discounting the 0.0001 BTC transaction fee he has to pay no matter what) than the approximately 0.001 BitBTC bond he would forfeit by just retracting his BTC balance. To prevent these types of scenarios, partial satisfaction of the bidder's obligation is allowed through the way the "BTC balance moved" transaction is designed to include the bit array rather than just a simple boolean. The size of the bit array wouldn't be too large. The bit array would be represented as a big unsigned integer (which would have to be less than 2^(N+1)) and then serialized as a varint. A reasonable upper bound on N could be prescribed by the blockchain (it is unlikely for the number of unique BTC addresses in the collective positions of the bidder to become very large normally anyway), and/or the blockchain could require that the fee of the "BTC deposit" transaction (and any "renew balance" transaction) to be of the form a + b*ceil(log(N)/log(2)), where a and b are blockchain prescribed constants and N is the parameter supplied by the user within the transaction.