drltc's Trustee Technical Discussion Thread

[AsymmetricInformation]

Let me clarify.

[1] I see that Gold is trading for $1000. Lowest ask: $1100, highest bid: $900. There are several asks above 1100.
[2] I feel that I would pay up to $1500 for 1 Gold. "What a deal! They're just giving it away...I can't wait to make another gold-plated N64 controller!"
[3] I place a trade: 'Buy 1 Gold for $1100'

[4*] At this point, someone "runs in front" of my trade (knowing that I want it at $1100), and places their own 'Buy 1 Gold for $1100'

[4*] Then I get frustrated...my order did not go through! I try again: 'Buy @ $1200', 'Buy @ $1300', 'Buy @ $1500'. Each time the trade is front-run and I don't get my gold!

The change in price does NOT have to be specific to me. What if I observed a gold mine collapse (decreasing the supply of gold and increasing its price)? In a world without front-running, I could profit by trading to reveal this information. However, if someone front-runs me, they'll get all the reward. Why should I even bother? Front-running destroys a market's ability to aggregate information. The problem is greatest in prediction markets, which directly concern information.

How does the matching algorithm discourage this from happening?

[AsymmetricInformation]

Lets address the issues here:

1) front running ... this particular issue does not apply given my matching algorithm.  The person placing the order will get the same price regardless of what any other party does.   In fact, one could argue that the blockchain earns revenue by intentional front-running and that the shareholders are the ones to benefit from it.   

Suppose every buyer wants to maximize the probability that their order is filled, subject to the constraint that the price is less than HPBWP (Highest Price Buyer Is Willing To Pay).  Obviously, a buyer can achieve these goals by setting a bid price equal to HPBWP.

However, the person who assembles the block might have a better option which achieves the same goals.  Since they know all other transactions in the block, they can compute exactly where in the order their transaction will be.  They can then compute the best Ask price at that point in the sequence, and set their order to that price (Best Ask At Time Of Execution or BAATOE).

There is value in the spread HPBWP - BAATOE.  One goal of BitShares X is to capture this value and return it to shareholders.  If the person who assembles the block has the capability to input their own transaction as the last transaction in the block, they can effectively circumvent the capture mechanism and extract the value for themselves.

My solution is a protocol design which requires all transactions to be signed by several randomly chosen notaries to be included in a block.  Thus a single notary or a small group of colluding notaries cannot perform the above attack.

I request a follow-up to this from Bytemaster, as it seems that the proposed matching algorithm actually does not prevent front-running, nor mitigate the (very real) damage.

[theoretical]

reordering .... this particular issue is not possible, because orders are sorted/matched deterministically...

My picture of the market is as follows:

0. Create a list called the "book," initially empty.  Create another list called the "input", fill it with all the orders in the block.  Create a third list called "output", initially empty.

1. Insert the next order from the input into the book.  If no input is available, stop.

2. If the best bid and best ask in the book overlap, go to step 3.  Otherwise, go to step 1.

3. Match a bid order and an ask order in the book.

4. Put the resulting trade in the output list.

5. Subtract the filled quantity from the quantity field of both orders.

6. Remove any order with zero quantity from the book.

7. Go to step 2.

In this picture, it seems the word "determinstic" must mean "the specification prescribes a particular way to choose which bid and ask order to match in step 3," since that is the only ambiguous step in the algorithm.  It is not exactly clear what is "sorted."  In particular, the word "sorted" may refer to the fact that a data structure that maintains sorted order, such as a red-black tree, is a convenient way to implement the book.

My point was that a new step should be added between steps 0 and 1 which sorts the input.  Otherwise, manipulation may be possible.

Also, I'd like to point out that reordering is an example of the general concept of "malleability," which means "a method of transforming a transaction or block that preserves its validity but changes its semantics."  Of course the infamous Bitcoin transaction malleability would be another example.  Malleability in general is bad; protocol designers should strive to avoid malleability.

[theoretical]

Lets address the issues here:

1) front running ... this particular issue does not apply given my matching algorithm.  The person placing the order will get the same price regardless of what any other party does.   In fact, one could argue that the blockchain earns revenue by intentional front-running and that the shareholders are the ones to benefit from it.   

Suppose every buyer wants to maximize the probability that their order is filled, subject to the constraint that the price is less than HPBWP (Highest Price Buyer Is Willing To Pay).  Obviously, a buyer can achieve these goals by setting a bid price equal to HPBWP.

However, the person who assembles the block might have a better option which achieves the same goals.  Since they know all other transactions in the block, they can compute exactly where in the order their transaction will be.  They can then compute the best Ask price at that point in the sequence, and set their order to that price (Best Ask At Time Of Execution or BAATOE).

There is value in the spread HPBWP - BAATOE.  One goal of BitShares X is to capture this value and return it to shareholders.  If the person who assembles the block has the capability to input their own transaction as the last transaction in the block, they can effectively circumvent the capture mechanism and extract the value for themselves.

My solution is a protocol design which requires all transactions to be signed by several randomly chosen notaries to be included in a block.  Thus a single notary or a small group of colluding notaries cannot perform the above attack.

[bytemaster]

Doesn't a "market order" always take precedence over a "limit order"?

There are no "market orders" and "limit orders" do not ever pay you a better price than you asked for.

Limits would be what creates the bid/ask spread book.  Market orders are what triggers the a bid/ask quote and would be someone who takes current going rate for which ever end they are playing. This is usually used for those wanting to jump in and not wait for the market move to a specified price.

Limits will pay better if price gaps but likely won't happen if the market is liquid and open 24 hr/day.

Perhaps I should not compare this to the stock market?

The algorithm is very simple because it is not a first-come-first-serve system.  So many traditional order types do not apply or could result in manipulation. 

[NewMine]

Doesn't a "market order" always take precedence over a "limit order"?

There are no "market orders" and "limit orders" do not ever pay you a better price than you asked for.

Limits would be what creates the bid/ask spread book.  Market orders are what triggers the a bid/ask quote and would be someone who takes current going rate for which ever end they are playing. This is usually used for those wanting to jump in and not wait for the market move to a specified price.

Limits will pay better if price gaps but likely won't happen if the market is liquid and open 24 hr/day.

Perhaps I should not compare this to the stock market?

[bytemaster]

Doesn't a "market order" always take precedence over a "limit order"?

There are no "market orders" and "limit orders" do not ever pay you a better price than you asked for.

[NewMine]

Doesn't a "market order" always take precedence over a "limit order"?

[bytemaster]

Lets address the issues here:

1) front running ... this particular issue does not apply given my matching algorithm.  The person placing the order will get the same price regardless of what any other party does.   In fact, one could argue that the blockchain earns revenue by intentional front-running and that the shareholders are the ones to benefit from it.   


As you can see here... if you see a low ask... you cannot front run it by placing a higher bid to be the first in line to get that low price.   If you see a high bid, you cannot front run it either.   

2) reordering .... this particular issue is not possible, because orders are sorted/matched deterministically...

3) your only control is excluding bids or asks.  Fortunately the market making algorithm also makes this form of manipulation irrelevant as well because it will not effect the price people get for their orders.   Remember, you get what you asked for or nothing.  When you place a bid the assumption is that the offer is good for at least a couple of blocks and therefore don't trade if you need depend upon high frequency noise.   

The result of this matching algorithm will be a wider bid/ask spread but a more meaningful one. 

[theoretical]

Therefore, I am expecting the same kind of behavior from users of BTS X except instead of having to point their hashing power at a pool, they merely change a setting in their wallet.  This setting can even be setup with a chain of command so that users do not have to think much about it.  Instead of only miners voting, everyone can vote.

I wonder if "chain of command" means the concept I've been calling "transitive proxies."  By "transitive proxy" I mean a relationship where you can assign someone to vote on your behalf, and they can assign someone to vote on their behalf, et cetera.  It seems like a good idea because it lets small shareholders delegate their votes to someone they personally know and trust, who has a better grasp of the issues and responsibilities of voting, and perhaps spends more time following the BitShares world.  That person in turn can delegate their votes to someone they know and trust.  So everyone deals with people they know who can explain things, those to whom responsibility is dedicated often have a finite number of persons to please or persuade, and small shareholders can pass off the responsibility to stay informed and be available.

There are two potential problems with transitive proxies:  Cycles and long chains.

For example, say Eve has N small addresses with tiny balances.  If she combines them into a single large chain, she might be able to cause every node to do O(N^2) computation using O(N) transactions.  E.g. maybe she repeatedly creates a new address and tells it to delegate to the first address in her chain.  Then each added address requires walking all the way to the end of the chain to discover where the votes end up.

If try to fix the above problem by adding a field to the data structure to keep track of the ultimate destination where everyone's votes end up, then a chain built in the other direction becomes just as problematic.  So if Eve creates a new chain by always telling the last node to delegate to a different address, then changing the last node's delegation requires the ultimate destination of all prior nodes in the chain to be changed.

Okay, maybe we should just forbid long chains?  In that case, Eve can actually block a level 1 node from becoming a level 2 node by attaching a chain just under the length limit to it.  You might suppose the proper thing to do, then, is to allow the level-1 node to transition to level 2, and just cut off the now-too-long chain where it bumps against the length limit.  But this doesn't work either; if Eve is a level 1 node with followers, she can change from level 1 to level L-k by delegating to a chain of her own addresses, cutting off links between nodes further down the chain.  However, this may not be a problem.  It reduces Eve's vote total, reducing her influence on the network; the mischief she causes by causing the connections to be broken is less than she's costing herself to perform the attack.  In addition, now there's a public record that Eve's the sort of person who jumps levels, and should be obvious if the chain Eve's jumped to is a bunch of sock puppet accounts with tiny balances delegating to each other.

[theoretical]

I have spent the past several posts applying my previous thoughts to the political election proposed here:  https://bitsharestalk.org/index.php?topic=3955.0   In this post I will discuss a problem unique to that proposal which has a simple solution.

Lack of quorum situations can arise depending on the wealth distribution.  If 1% of all outstanding XTS is required to be a trustee / notary / representative ("notary" in this post), but there are 200 people with exactly equal balances of 0.5% XTS who all vote for themselves, then nobody is eligible to be a notary.  If the network is designed to require at least one notary to be online in order to operate, this is a problem.

I propose instead fixing the number of notaries NOTARY_COUNT (~32?  64?), then selecting the NOTARY_COUNT eligible candidates with the greatest vote total.  An "eligible candidate" meets the requirements for office:  So far, the only established requirement is publishing a transaction posting a bond.  To this I would add you must not have been an active notary for at least 72 hours (this should prevent oscillating when two candidates with frequently changing vote totals are nearly tied for last place).

[theoretical]

This post discusses an algorithm for choosing a proposer set randomly.  I suggest ordering the notaries by sorting with H(H(shiftreg) + H(notary_pubkey)) as
the sort key.  The value shiftreg contains the low bit from the last 128 hashes.  If we used the hash of the previous block instead, then a number of colluding
notaries might fall early in the order by chance.  Then they would be able to front-run the next block and manipulate the next block's hash at will.  They
could then "mine" a block hash that results in a favorable ordering for the *next* block hash, and maintain control for multiple blocks.  This attack would
leave irrefutable statistical evidence after a time.  But shiftreg is a trivial modification that makes it much harder for this attack to maintain control for several blocks:
If the colluders by luck obtain a favorable ordering, they can still front-run the next block and manipulate its hash, but they can only choose from two
possible orderings for the next block; unless the colluding group is very large, there will be a very high probability that neither choice allows them to
maintain control.  I call this attack the "notary ordering selection attack."

The proposer set is just the first TXSET_QUORUM notaries in the ordering; any that fail are replaced by the next ones in the ordering.

[theoretical]

Front-running and transaction censorship via selective deafness are problems with both random notary selection and political voting.  The solution I proposed for randomly selected notaries
in this post https://bitsharestalk.org/index.php?topic=3895.msg49007#msg49007 involves generating txsets.  In this post, I will develop a similar alternative protocol to fit better with a
political voting design.  This protocol implements the following restrictions on notaries:
(1) Avoid giving a notary exclusive power to decide which transactions will be included ("transaction censorship"),
(2) Avoid giving a notary the ability to include non-public transactions ("private placement"),
(3) Forbid a notary from inserting a transaction at the last moment ("front-running").

The new protocol is a simple variation of my previously proposed txset protocol.  Rather than have randomly chosen nodes propose txsets, have notaries propose
txsets.  Additionally, since notaries are more reliable than randomly chosen ordinary nodes, use a commitment protocol instead of a simple broadcast, so blind
to the transactions that are included.

The "primary notary" is the notary that is supposed to produce the next block.

First, we choose a set of notaries that participate in choosing the transactions for the next block.  Call this set the "proposer set."  If the members of
the proposer set collude with each other, they will be able to perform transaction censorship, private placement and front-running.  A larger set will
increase security by increasing the amount of collusion necessary for a successful attack, but also has a cost of increased blockchain storage.  I will
discuss how to reduce the size of the proposer set in a future post, but an easy and secure way to choose the proposer set is the maximal choice:  Simply
put every notary except the primary notary in the proposer set.

The size of the proposer set is TXSET_QUORUM for consistency with my previous posts.  Each proposer signs and broadcasts a txset commitment hash, which
is simply the Merkle root hash of a nonce (chosen randomly locally) and the list of hashes of transactions the proposer believes ought to be included
in the block.  However, proposers do not immediately broadcast the transaction list used to create the txset commitment hash!  After receiving the
txset commitment hash, the notary issues a block commitment.  The block commitment is a signed hash of all the txset commitment hashes for the txsets
that will be included in the block.  Once a proposer receives a block commitment from the primary notary, it broadcasts ("reveals") the txset contents
and nonce corresponding to its previous commitment.  The block can be validated when all proposers' block commitments are revealed.  Finally,
the primary notary signs the block one last time, which finalizes it.

I've left out descriptions of the timeouts necessary to deal with offline notaries in the above protocol.  But basically, whenever one or more of the notaries
doesn't respond and appears to be offline, the algorithm should replace the offline node(s) by the next available node(s) and restart from the top.
Timeout implementation considerations are the rationale behind the finalization step.  Finalization is really a barrier to avoid a race condition
where all proposers reveal, but the timeout expires before the reveals reach the primary notary (perhaps one or more of the proposers is slow).  The
protocol restarts with a new proposer set that doesn't include the slow members of the previous proposer set.  All the reveals from the original proposer
set might reach some nodes, which would be able to put together a complete block; meanwhile the notaries have started working on a different block,
and that information might not have gotten very far.  The nodes that have received all the reveals can assemble them into a complete block, but it
won't be able to proceed without the finalization signature.  This is a "fork", but a very limited one:  The wrong branch will never grow beyond
a single block; clients understand that the block is not yet immutable, the transactions therein still pending.

[theoretical]

First, a terminology note.  We've already had a change in term from "trustee" to "notary."  Now apparently the new term is "representative."
However, I don't want to do another terminology change; for the moment I will continue to use the term "notary" in this thread to describe the entity that produces blocks.

With respect to randomly selecting notaries vs. voting for notaries, I now believe that voting for a notary can be made to work.  Discussion in the current thread has been quite productive
on the issue.  I believe bytemaster's proposal in this thread https://bitsharestalk.org/index.php?topic=3955.msg49823
will basically work, but can be improved with a few adjustments I will describe in future posts.  Therefore I basically
support that proposal.

In the interest of discussing alternatives and tradeoffs, in this post I will explain how random selection can also be made to work.  Random selection has at least one compelling selling point
that voting does not, but random selection is also more complex to implement, and has at least one drawback compared to political voting.  This is the nature of designing any complex software application:
You often are faced with tradeoffs; which solution is "best" depends on how you weigh the different strengths and weaknesses of each solution.

The main problem I've always had with political voting solutions:  Voter apathy.  It's hard to get people to vote manually, in a timely, informed manner, without being deceived by candidates' marketing tricks.
Further, I believe it is not unreasonable to expect many people to vote for their client's default choice.  If the default choice is hard-coded, that candidate will get an unfair boost from the uninformed masses who
just stick with the default choice.  If the client picks the default candidate randomly, or abstains from voting by default, you're at least no longer giving one candidate a grossly unfair advantage.

With random selection of notaries, the voter apathy problem can be decisively solved.  There is a viable, known-honest node that can be set as a default in the client code:  The local node.

Three main objections were raised by bytemaster.  I did actually think about them before I proposed random selection of notaries:

1) high probability they are not online

Nodes that are offline cannot be selected.  If a node goes offline between its selection and execution, the failover is fast enough that the network only experiences a small delay.

2) attackers would gain control proportional to their stake without any peer review...

The entire point of both voting and random selection is that everyone gets control proportional to their stake.  I don't know what is meant by "peer review."

3) without any mining at all, the generation of a random number in a decentralized manner is impossible and thus an attacker could control the random number generation.

This is not true.  Take one bit from N adjacent block hashes, then hash the result with your public key and the current time, measured in ticks from the last block (one tick is about 50 ms).  To get k bits of control over the random number generator and thus amplify their effective power by 2^k, the attacker must control k adjacent block hashes.  If you divide the random number by your balance, then the probability you produce a hash smaller than some target is proportional to your wealth.

The strength of random selection is getting apathetic voters to vote for a known-good notary (the local node).  The weaknesses are the complexity of the implementation and brief downtime when a notary goes offline.  Earlier in this
thread we discuss how this downtime can be limited (one minute seems like it would be practically achievable).

[stuartcharles]

Respect to DrLtc, Bytemaster and the rest of you problem solvers