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.

[Edit: I actually think this is one of the weaknesses of BitAssets at this stage, in that issuance requires BTS bulls to take a view that BTS will do better than the underlying asset, when these underlying assets may be unpredictable. In turn this makes the entire system liquidity reliant on the existence of very strong BTS bulls. Shorts are effectively borrowing in the underlying asset to fund their position in BTS. The availability of new issuers (i.e. shorts) may be improved and more consistent if there were a simple way for issuers to profit from the pure service of issuing bitAssets without having to take directional views. Arbitrage has some practical issues though.]

How could such a thing be possible? Of course BitAssets require the shorts to believe BTS will do better than the underlying asset. That is the only way (as far as I can imagine) to motivate the shorts to risk their BTS supporting the BitAsset price. If you are able to somehow take away that risk from the shorts, I can't imagine how the BitAsset could maintain its peg anymore without anything of value backing it.

Alright, I have another approach that uses this threshold scheme, the previous ECDSA threshold scheme (with the t' = 2*t - 1 limitation), and Bitcoin's multisig. This scheme is more flexible. When delegate participation is at least 93, the reserve cannot be compromised by a colluding group of less than 49 delegates. If delegate participation drops below 93, it is possible (under normal circumstances) to enter a recovery mode in which the reserve can be recovered by at least 73 participating delegates (however, between the time of entering this recovery mode and fully recovering the reserve, the reserve is vulnerable to a colluding group of 28 delegates).

Procedure:

Segment the top 100 delegates into 10 disjoint regions of 10 delegates each. Each region can use a 7-of-10 threshold scheme (the one without the t' = 2*t - 1 limitation). This requires setting up (10 choose 7) = 120 different 7-of-7 subsets for each region. Since signature generation in each region will require a 7-of-7 scheme, it means it will require 19 rounds and take approximately 30 seconds.

If 97 of the top 100 delegates participate in a threshold signature scheme (the old t' = 2*t - 1 limited one) to create a backup key, it means 49 of the top 100 delegates can collude to recover the backup private key.

We can require a 9-of-15 multisig to protect the reserve where 10 of the keys are the threshold public keys for each region and the remaining 5 keys are copies of the backup key.

If the right 49 delegates collude they can generate 7 signatures corresponding to 7 of the first 10 keys in the multisig, as well as recover the backup key for a total of 8 signatures corresponding to 12 of the 15 keys (this satisfies the 9-of-15 multisig). However, if any 48 of the top 100 delegates collude they can only generate 6 signatures corresponding to 6 of the first 10 keys in the multisig and they cannot reconstruct the backup key and therefore do not have the necessary signatures to compromise the reserve.

Under normal operation, the backup key should not be used. In this case all 9 signatures must come from regions. In the worst case scenario (in terms of halting the gateway), all 10 regions could have at least 6 participating delegates each (total of 60 so far) and in addition 8 of these 10 would each have all 10 participating delegates. This gives a total of 92 participating delegates but only 8 signatures. To generate the last signature under normal operation would require one more participating delegate for a total of 93 of the top 100 delegates participating.

However, under fallback operation the backup key could be recovered and so only 4 signatures corresponding to the first ten keys would be needed. In the worst case scenario (in terms of halting the gateway), all 10 regions could have at least 6 participating delegates each (total of 60 so far) and in addition 3 of these 10 would each have all 10 participating delegates. This gives a total of 72 participating delegates but only 3 signatures. To generate the last signature one more participating delegates would be needed for a total of 73 of the top 100 delegates participating. Also, when one of the chosen delegates is able to recover the backup private key this delegate could collude with a minimum of 27 other delegates to compromise the reserve. Thus in fallback mode the minimum number of colluding delegates needed to compromise the reserve is actually 28 not 49.

Finally, if it was not possible to get at least 97 of the top 100 delegates to participate in the generation of the backup key, then this scheme must fallback to using a 7-of-10 multisig instead where the 10 keys are again the threshold public keys for each region. In this case, if less than 85 of the top 100 delegates are participating, the reserve could potentially be stuck. Also, it would take a minimum of 49 of the top 100 delegates to collude to compromise the reserve.

Summary:

As long as the backup private key is never reconstructed (only needs to happen during fallback operation), then it is not possible for less than 49 of the top 100 delegates to ever compromise the reserve by colluding together. If the private key is reconstructed during fallback operation, then 28 colluding delegates of the top 100 delegates could potentially compromise the reserve if the private key was reconstructed on the machine of a delegate that was one of the colluding 28.

There are three different modes of operation: normal mode, no-fallback-available mode, fallback-activated mode. There is a minimum number of participating delegates for each mode that will guarantee that the gateway will be able to function (below that number it is possible, but not necessarily likely, that the gateway will halt unless the fallback operation is activated if possible). Under normal mode, if at least 93 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, it is possible to active fallback operation). Under no-fallback-available-mode, if at least 85 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, there is no fallback to rely on). Under fallback-activate mode, if at least 73 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, there is no additional fallback to rely on).

When initiating the scheme, normally the keys and multisig will be set up to allow normal mode of operation. This however requires at least 97 of the (new) top 100 delegates to participate in the set up process for the keys each time the set of top 100 delegates changes. If this is not possible at the time of a change to the set of top 100 delegates, then the keys and multisig will be set up (with the new top 100 delegates) to allow a no-fallback-available mode of operation. During the no-fallback-available mode, if at any time at least 97 of the top 100 delegates become available (even without the set of top 100 delegates changing) the keys and multisig can be updated (and the Bitcoin reserve moved) to upgrade the mode of operation back to normal mode.

By the way, this new threshold signature scheme combined with Bitcoin's multisig features provides better security properties for the BitShares Standard Gateway proposal without having it be too computationally inefficient.

With the previous threshold signature system there was the t' = 2*t - 1 restriction. That means with a 46-of-101 threshold scheme (t = 46, n = 101, t/n = 45.5%), it required t' = 2*t - 1 = 91 participants at a minimum to work together to generate a signature. This means with less than 90% delegate participation the gateway would halt and the reserves would be stuck. If I were to only look at the top 98 delegates rather than the top 101, and bump up the delegate participation requirement to 95%, this would give a value of n = 98 and t' = 93, which means t = (t' + 1)/2 = 47. So this would be a 47-of-98 threshold scheme (t/n = 48%).

However, with this new threshold signature scheme combined with multisig (Bitcoin should now allow up to 15-of-15 I believe) can let us do better. First I divide the top 98 delegates into 14 disjoint regions each consisting of 7 delegates. For each region, the 7 delegates in that region initialize (7 choose 2) = 21 5-of-5 threshold schemes, one for each of the 21 unique subsets consisting of 5 delegates from the 7 in the region. Through this initialize process, each region should come up with its own threshold public key for that region. The Bitcoin reserve is then a 13-of-14 multisig where the 14 keys are the threshold public keys from each of the 14 regions.

Under this scheme, the worst case scenario for halting the gateway is if 2 regions are unable to generate a threshold signature. For a region to not be able to generate a threshold signature, there must be at least 3 of the 7 delegates in that region that are not participating. So that is a total of 6 delegates, at a minimum, from the top 98 that must be not participating. Therefore, the gateway will not halt if at least 93 of the 98 delegates are participating (n = 98, t' = 93, just like in the previous version stated above). However, the previous version had a t = 47, while this version has much better security properties. In the worst case scenario, it takes 13 regions to generate signatures for a malicious transaction and each of these regions would generate the signature with the minimum 5 delegates participating in the threshold signature scheme for each region. So that is a minimum of 65 delegates that need to collude to compromise the reserve (t = 65, t/n = 66.3%). This is much better than in the previous version stated above. In the previous version a colluding group of at least 48% of the top 98 delegates could compromise the reserve, but in this version a colluding group of at least 66% of the top 98 delegates could compromise the reserve.

Another option is to make the multisig 11-of-14 and the threshold scheme of each region 6-of-7. In this case halting the gateway requires at least 4 regions to be unable to generate a threshold signature and each region requires 2 non-cooperating delegates, which would at a minimum require 8 non-cooperating delegates. This means if at least 91 of the 98 delegates are participating the gateway with not halt (n = 98, t' = 91). The minimum number of colluding delegates required to compromise the reserve would be 66 in this case (t = 66, t/n = 67.3%). You can see the table of tuples (t/n, t'/n) for a variety of possible solutions using a similar scheme here.

Finally, what about computational efficiency. First, requiring the delegates in each 5-of-5 region to store 21x the number of secrets is not a big deal (it is even less of an issue to store 7x in the case of 6-of-6 regions). Also doing 21x (or 7x in the 6-of-6 case) computations in parallel each time the number of delegates in that region changes is also no big deal. The more interesting metric is how long it takes to generate signatures for the 5-of-5 or 6-of-6 threshold scheme. It would take only 3*5 - 2 = 13 rounds to generate the signature for each 5-of-5 region and only 3*6 - 2 = 16 rounds to generate the signature of each 6-of-6 region. The amount of time it would take to do this (according to the paper) is approximately 10 seconds for the 5-of-5 regions and less than 20 seconds for the 6-of-6 regions.

The challenge is that the single operation is "unbounded" in the number of accounts it would have to credit.   If there are 1M people that need to receive the dividend then that single operation could take a very long time to apply and that would disrupt the flow of the network.

Recognizing this as something that would be nice to automate I will think about it.  It is not on our current issue list on github though.

It doesn't have to. You can simply record a dividend event for each UIA. For example, UIA-1 could have a dividend event at block N for a total of X BitUSD when the total UIA-1 supply at this time was Y UIA-1 (it would also record a mutable value of the accumulated amount of UIA-1 moved to claim this dividend, which starts with 0 always). It also stores that original X BitUSD in a pool associated with UIA-1. When someone is moving their UIA-1 they can collect the appropriate amount of yield in the form of the BitAssets distributed as dividends since the last time they movied their UIA-1.

So, let's say a UIA-1 balance existed prior to block N with a quantity of y1 UIA-1. There would be no way to add more UIA-1 to that particular balance anymore after the dividend event. A user could withdraw some portion of UIA-1 in the balance and deposit it to a new balance that exists after block N. If the user withdrew y2 UIA-1 out of that balance during a block after N, then the user would automatically receive (y2/Y)*X BitUSD from the pool as part of their transaction to be deposited wherever they wish (by default would be deposited to a new BitUSD balance with a condition identical to the one of the UIA-1 balance being withdraw from). The system would also add y2 to the accumulated amount of UIA-1 moved to claim the particular dividend. When the accumulated amount of UIA-1 moved to claim the particular dividend becomes equal to Y, the system knows that all of the dividends for that particular dividend event have been claimed (there might be some extra BitUSD in the pool because of rounding down, which is just free money that can be claimed back by the UIA-1 issuer).

There is the issue that if there are multiple dividend events that occur between the time a balance exists and the time it is moved, the system will need to do the above calculation for each of those dividend events. But the point is that this scales with D, where D = the number of dividend events, rather than with N, where N = the number of UIA-1 balances. I expect dividend events to be relatively infrequent that this wouldn't be a significant problem. It could also be possible to put a bound on D by having the ability to claim dividends expire. For example, if a UIA-1 holder doesn't claim the dividends of a dividend event that is more than 24 dividend events old, they would forfeit their right to claim the dividends of that dividend event (they could still claim the dividends of the most recent 24 dividend events though). This could be implemented by automatically setting the accumulated amount of UIA-1 moved to claim the dividend for that particular dividend event to its respective Y value, which would then allow the issuer reclaim the remaining unclaimed dividends for that dividend event. This would put an upper bound of 24 on D, which I think is reasonable when you consider that even if dividends are as frequent as once a month, a dividend receiver will not lose any dividends as long as they claim them (meaning move all of their UIA balances) at least once a year.

My hunch is major and sudden changes like that won't be possible if ecosystem businesses are large enough - another way, how much effort would it take all Bitcoin businesses to upgrade to an entirely newly designed blockchain

Downloading and installing a new piece of software? Assuming the RPC API was unchanged and the forking was instantaneous, I can't imagine it would be much effort for users to upgrade their clients. Also, the upgrade would only go into effect when more than 75% of BTS stake votes in favor of the upgrade.

We need to remain agile enough to make large, significant changes gradually over time with smooth transitions. Delegates and stake voting help with this process. We don't want the technology to ossify and stagnate like Bitcoin because then that leaves us open to inevitably being replaced by a better technology despite any advantages in network effect.

Quote from: hadrian on March 05, 2015, 05:45:51 pm

• Technical aspects - is Rust really THAT good? Is this something we should or could consider at any point?

I've been following Rust for a while with extreme interest and would absolutely consider it as my #1 choice for a FUTURE (after a year or two) project. It still has not hit 1.0 and I would expect another year or two for an an acceptable ecosystem of libraries, etc. to develop.

  My hope is that in a couple years we take all the lessons learned from BitShares development and usage and reimplement the entire platform the best way we know how at the time, this time written entirely in Rust, and release it as BitShares 3.0 whose genesis block contains a commitment to a genesis database state which is a live snapshot of the most recent state from the BitShares 2.x chain it instantaneously replaces.

What makes it difficult is that I envision a very large overhaul being needed, rather than quick and messy proposal vote system being slapped together without anonymity and without access to all voters due full client usability problems (which are improving but still have a fair distance to go).

Forget privacy, that is way too difficult to implement. I think a hacky solution (as ugly as it is) is the best way to go at the moment. We don't even need to hard fork the blockchain (although I would prefer to do so using a specifically designed proposal submission transaction). We can create an account whose wall is specifically meant for proposal submissions. The protocol could require the burn message to start with some keyword followed by a space and then a version number and then another space and then a digest of the proposal contents, and the burn amount would need to be positive and equal to some constant F amount of BTS that we define as part of the protocol. If a burn message meets these criteria it should be considered a proposal submission and the digest is the digest of the proposal content. We take all such burn messages in order of submission and number them sequentially starting from 1 (this is the proposal ID). The blockchain allows putting negative numbers in the delegate slate down to -2^31. I suggest that if a proposal has ID N, then if the negative number -(2*N) is included in the delegate slate it represents an upvote for proposal N and if the negative number -(2*N-1) is included in the delegate slate it represents a downvote for a proposal N (if both are included they cancel each other out and act as the default neutral vote which is equivalent to not including them in the delegate slate). This allows for 2^30 proposals (or roughly a billion). That should be more than enough for the time period that we use this hacky solution.

Everything else can be interpreted from the blockchain by the client. The delegates do not need to upgrade and no hard fork is necessary. You could even use a separate client to analyze the blockchain and tally the up and down votes for each proposal. However, the normal client would need to be modified for a user to be able to up or down vote a particular proposal. I would suggest providing a set of up to 111 unique negative numbers to the wallet (which is stored in the wallet database). Every time BTS is moved or update votes is pressed, the wallet should automatically add these numbers to the delegate slate of a BTS balance and the remaining slots of the slate are used to vote for delegates as usual. The user should be able to make changes to these set of negative numbers through the CLI but it should also ideally be possible to make the changes in a more natural way: something like proposal_update_vote <digest|ID> <up|down|neutral> which would use the indexed proposal database to automatically figure out how to do the correct thing; it should also be possible to visualize the current set of negative numbers in sensible format using a command like proposal_list_votes. However, in the worst case an outside script could use the CLI commands to update the set of negative numbers directly and provide this nice interface by tapping into the indexed proposal database created not by the main BitShares client but a separate outside utility that scans the chain folder (I prefer the in-client solution).

Although the UI described above is all CLI and I don't really expect GUI support in the client initially, it would be great if bitsharesblocks.com could visualize the tally for the submitted proposals so that people could easily view them from their web browser. It would also be really cool if bitsharesblocks.com stored the actual contents of the proposal and displayed it to users. Anyone could submit the content because the website would take the digest of the content and compare it to the digest of the proposal on the blockchain and only accept the content submission if the digests matched. If a sensible size limit was provided for the proposal contents and the value of the fee F chosen was reasonable, there would be no spam/abuse issues. Of course one could also just host the proposal content anywhere (say a post on this forum). Users could copy and paste the contents to the proposal page on bitsharesblocks.com and the web page would locally compute the digest and check if it is valid by comparing it to the actual digest of the proposal as determined from the blockchain.

So is this minimal developer effort worth it? Personally, I think we need better cold storage and restricted_owner support first. And not just blockchain and CLI support but GUI support and usable UX. Otherwise, I worry that voter apathy is just going to remain bad and the proposals will be of limited value. But after that I definitely think it is worth it to have at least this basic feature set so that we can actually give a fair voice to the shareholders. The good news is that it doesn't require any additional hard fork changes and so doesn't require consensus from all the delegates. Also a lot of the code (tallying the blockchain and visualizing the tally) could be done without any core dev support. But I think it is important to have an official wallet feature (even if only CLI) that allows the user at a minimum to specify some number of negative ints to vote for in BTS balances before using the rest of the delegate slate to do the traditional delegate voting. I wonder if pc would be interested in enabling such a functionality that could be merged into the official wallet (like he did with computing the balances of an account at an arbitrary point in time)? His delegate isn't in yet, if he is interested in enabling this then maybe shareholders interested in this idea could then vote him in as a way of showing support for this proposal (I think they should vote him even if he doesn't want to do it too). Anyway, if he doesn't want to do it I'll see if I can find the time to get something working, but it might take a while before I have enough free time to work on this (plus I don't want to waste my time on it if the community won't find it desirable).