BitShares Forum

Main => General Discussion => Topic started by: theoretical on March 29, 2014, 11:28:02 pm

Title: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 29, 2014, 11:28:02 pm

I dislike the trustee concept.  But the more I thought about it, the more I realized that we really don't know any technical details.  So far, the only information I've seen is that the new system will involve a single centralized entity. 
Countless words on this forum have already been devoted to the various strengths and weaknesses of the trustee from legal, regulatory, and marketing perspectives.  Those are surely worthy issues, but if you'd like to pursue them, please do so in a different thread.  I'd like this thread to be solely about technical specification and analysis of cryptocurrency designs that incorporate the trustee concept (with perhaps a little economic analysis as well).

This is a very recent direction change, and I'm not sure that bytemaster or anybody else has publicly discussed detailed technical mechanisms that might be used in a trustee-based BitShares X.  The goal of this thread is to begin that discussion.  Legal, regulatory, marketing, and economic perspectives are off-topic (but may be tolerated if they inform technical decisions).  The primary focus is discussing the practical engineering concerns of trustee-based cryptocurrencies, with a focus on how BitShares X should work.

If you like my analysis in this thread, and want to know my thoughts on how a non-trustee-based BitShares X should look, you can read all about that at https://github.com/drltc/xts-proposal -- and you can also donate PTS to the address there.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 29, 2014, 11:28:39 pm

To start off with, I'll examine the technical reasons for a trustee design.  My understanding is that the trustee design is bytemaster's attempt to solve two problems with a random method (Poisson process):  (1) Sometimes blocks are generated too far apart.  This is annoying; users would have a better experience if the wall-clock time between blocks was predictable.  (2) Sometimes blocks are generated too close together.  If the interval between two blocks is smaller than the network propogation delay, this is the beginning of a fork.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 29, 2014, 11:28:56 pm

In this post, I'll discuss two broad design flavors for trustee elections:  "political" elections and "technical" elections.  In "political election," the trustee is chosen by what is basically a traditional democratic process (well, more like a corporate election process as the weight of your vote is determined by the number of coins you hold).  A trustee is a human with a known identity (or at least a pseudonym), and convinces shares to vote for him (or her) by convincing humans to manually enter the candidate's public key in the "I vote for this person" field.  A political election scheme would probably have any trustee in office for months or years, barring impeachment.  Political elections suffer from many problems.  I believe bytemaster's intent is to have political elections.  By contrast, in a "technical election," the trustee is chosen by some automatic process.  I propose the trustee should be chosen randomly from all online nodes (weighted by number of coins), and serve for a limited term (10-1000 blocks, a term measured in hours or days).  If a trustee loses network connection, a replacement should be elected after some timeout interval.  A traditional proof-of-stake random selection method could be considered an example of a technical election with a one-block term.

I believe technical election is superior to political election in the context of cryptocurrency trustee designs.  Much of the analysis to date -- including many of the objections to the trustee concept that have been raised -- apply only to designs involving political elections.  Political elections require some amount of conscious, manual actions by humans representing a large share of the network, but technical elections can happen entirely without human intervention.  Thus, systems using technical elections can quickly replace an offline, malfunctioning, or malicious trustee, without waiting for the humans to notice the situation, arrive at a decision that's acceptable to a majority, and convince that majority to actually vote.  (Anyone who pays any attention at all to real-world politics should realize that each of those steps may prove to be a major obstacle in practice.)  Further, since the choice of candidates and the election process are fully automated, it is practical to hold technical elections very frequently.  Therefore the term length can be set fairly short, which greatly reduces the influence that any one trustee can have on the system.  Finally, technical election can set unambiguous rules for resolving ties, or results where no candidate receives a majority.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 29, 2014, 11:30:43 pm

In this post, I'll discuss two potential attack vectors for trustee-based systems.  A trustee may pretend that they haven't received certain transactions, either because they wish to censor those transactions, or to gain some advantage.  I call any attack based on ignoring network communications a "selective deafness attack."   A trustee may also use their control of, and information about, the unpublished exact details of the next block in order to gain some advantage.  The simplest example of this is that a trustee can avoid a mismatch between their order and what the market is willing to pay; they know exactly what the best bid / best ask will be, and can construct their transaction to match.  I call this "trustee front-running."

As I've pointed out in other threads, existing networks like Bitcoin that randomly select "trustees" who serve a one-block "term" have protection against selective deafness attacks, simply due to the fact that the trustee will quickly be replaced, and it's difficult to get all Bitcoin miners to agree that a certain transaction is unacceptable (unless of course the transaction attempts to spend money that doesn't exist, has an invalid signature, or is otherwise corrupt / violates the spec in some way).  So there's a high probability that, within a few blocks, at least one miner will accept any given transaction.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 29, 2014, 11:31:00 pm
In this post, I'll propose what I see as a practical design for a trustee-based system.

I propose a hybrid two-tiered system.  The higher tier is a single trustee that generates blocks using txsets provided by the lower tier.  The lower tier is responsible for generating txsets using a random (Poisson) process.  All online nodes participate in generating txsets using difficulty-adjusted proof-of-stake.  A txset consists of a proof-of-stake, a parent block hash, a list of transactions, and a signature by the key that generated the proof-of-stake.  When a txset is generated, it's broadcast (of course, to avoid abuse of the broadcast communication path, all nodes must validate the stake, signature, and transactions before propagating the txset).

The trustee must include exactly TXSET_QUORUM txsets in a block; otherwise the block is invalid.  Further, the transactions included in the block must be precisely equal to the set of transactions that occur at least TXSET_PLURALITY times in the block.  TXSET_QUORUM is a tradeoff:  Increasing it increases security, but costs broadcast bandwidth and blockchain storage.  I suggest TXSET_QUORUM = 8.  TXSET_PLURALITY is also a tradeoff.  A trustee with connections to many wealthy coin holders will be able to front-run if they and their allies are able to generate TXSET_PLURALITY different stakes.  Thus, increasing TXSET_PLURALITY makes front-running harder for the trustee.  The tradeoff is that a larger TXSET_PLURALITY delays transactions, since they are required to saturate the network further before they become eligible to be included in a block.  I suggest TXSET_PLURALITY = 5.  (As its name suggests, there is no intrinsic reason why TXSET_PLURALITY >= TXSET_QUORUM / 2, even though my suggested value obeys that inequality).

In order to pull off a selective deafness attack -- especially over multiple blocks -- a trustee would have to control an enormous percentage of the network's online coins.  Indeed, such consensus would be needed that a successful maneuver might be better described as "the trustee's desired protocol change was voluntarily adopted" than "the trustee carried out a successful attack."

Since txsets are generated randomly, it is possible for txsets to be generated too slowly for TXSET_QUORUM blocks to be available when the trustee wishes to generate the next block; under these circumstances, the trustee has no choice but to delay the next block until more txsets become available.  (One possible cause of slow txset generation include bad luck in txset generation.  Another possible cause is a downward txset generation capacity fluctuation that isn't yet reflected in the difficulty.)  To mitigate the effect of slow txset generation, the generation rate of txsets can be increased so that the expected number of stakes generated in the desired block interval is TXSET_OVERGEN * TXSET_QUORUM.  Like the other parameters I've discussed, TXSET_OVERGEN represents a tradeoff:  Increasing TXSET_OVERGEN reduces the probability that blocks are late due to insufficient txsets, but reduces the percentage of the lower layer that a trustee must control in order to effectively dictate which transactions will be included in a block.  I suggest TXSET_OVERGEN = 1.25.

My proposal has some protection against network splits:  If a split occurs, then txset generation capacity will greatly slow on the "wrong" side of the split.  If the split's resolved before the timeout interval, no fork will be created.  If a substantial fraction of the online coins prior to the split are on the trustee's side of the split, then block generation will continue at a reduced rate.  If the split's resolved after the timeout interval, there will be a fork, which will be resolved in favor of the side of the split that generated the longer chain.  Which, due to the timeout interval, will be the pre-split trustee's side of the split if the split is resolved quickly.  A longer split would be resolved in favor of whichever side of the split has more online coins, hence txset generation capacity.

A couple other details:  Each txset is required to be consistent, e.g. cannot contain double spends.  But since the block is a combination of txsets, the block may end up containing double spends; the trustee can't remove them because they can't override the decision of the txsets.  I propose the following solution:  Double-spend transactions resulting from txset combination are allowed in a block, but they turn into no-ops, and may be pruned once they are old enough to no longer be needed to validate the actions of the trustee.

Since transactions are not necessarily commutative and associative, transactions should be sorted according to some fixed deterministic order.  In particular, the trustee should not be able to control the order in which transactions execute.  I propose executing transactions in order of descending fee per byte (thus higher fee-paying transactions go first), with H(cur_txn + prev_txn) used to break ties, where cur_txn is the hash of the current transaction and prev_txn is the hash of the previously executed transaction (or all zeros if the tie is for the first transaction to be executed).

Also, it is possible to optimize the storage of txsets in a block, since we know that each txset's transactions are a subset of the block's transactions.  For each transaction in the block, create txset_inclusion_mask, a value of TXSET_QUORUM bits indicating which txsets included this transaction.  (With the suggested parameter value TXSET_QUORUM = 8, txset_inclusion_mask will be a single byte.)  Then the txsets and their Merkle hash can then be reconstructed from the block's transaction list and the txset_inclusion_mask values.  The Merkle hash is dependent on the ordering of the txset's transaction list, but we can simply require txsets to list transactions in sorted order.

With the above optimization, the overall storage requirements of my proposal are quite modest:  A constant per-block overhead of 8 proofs-of-stake and 8 signatures, along with a one-byte increase in transaction size.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: Agent86 on March 30, 2014, 12:33:33 am
Hi drltc,
I'm not sure you are accurate on the reasons for the trustee.

You wrote:
"My understanding is that the trustee design is bytemaster's attempt to solve two problems with a random method...  (1) Sometimes blocks are generated too far apart. (2) Sometimes blocks are generated too close together."

I don't think this is the reason for it.  I think the problem is that the only "random methods" involve both mining with all the potential centralization and waste that comes with mining, and also require people to leave their wallets open on a networked computer to prove their stake.  Both of these have big drawbacks; very few people want to risk their coins on a networked computer to participate in the mining/security.

You also wrote:
"A traditional proof-of-stake random selection method could be considered an example of a technical election with a one-block term."

I don't think there is such a thing as a problem free "traditional proof-of-stake random selection method"
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bytemaster on March 30, 2014, 02:17:44 am

In this post, I'll discuss two broad design flavors for trustee elections:  "political" elections and "technical" elections.  In "political election," the trustee is chosen by what is basically a traditional democratic process (well, more like a corporate election process as the weight of your vote is determined by the number of coins you hold).  A trustee is a human with a known identity (or at least a pseudonym), and convinces shares to vote for him (or her) by convincing humans to manually enter the candidate's public key in the "I vote for this person" field.  A political election scheme would probably have any trustee in office for months or years, barring impeachment.  Political elections suffer from many problems.  I believe bytemaster's intent is to have political elections.  By contrast, in a "technical election," the trustee is chosen by some automatic process.  I propose the trustee should be chosen randomly from all online nodes (weighted by number of coins), and serve for a limited term (10-1000 blocks, a term measured in hours or days).  If a trustee loses network connection, a replacement should be elected after some timeout interval.  A traditional proof-of-stake random selection method could be considered an example of a technical election with a one-block term.

I believe technical election is superior to political election in the context of cryptocurrency trustee designs.  Much of the analysis to date -- including many of the objections to the trustee concept that have been raised -- apply only to designs involving political elections.  Political elections require some amount of conscious, manual actions by humans representing a large share of the network, but technical elections can happen entirely without human intervention.  Thus, systems using technical elections can quickly replace an offline, malfunctioning, or malicious trustee, without waiting for the humans to notice the situation, arrive at a decision that's acceptable to a majority, and convince that majority to actually vote.  (Anyone who pays any attention at all to real-world politics should realize that each of those steps may prove to be a major obstacle in practice.)  Further, since the choice of candidates and the election process are fully automated, it is practical to hold technical elections very frequently.  Therefore the term length can be set fairly short, which greatly reduces the influence that any one trustee can have on the system.  Finally, technical election can set unambiguous rules for resolving ties, or results where no candidate receives a majority.

Thanks for starting this thread... I look forward to seeing the results.   Some quick thoughts:

1) Lets use the notary name rather than trustee because it conveys the responsibility.
2) The technical elections can be manipulated by the false assumption that large stakes indicate trust.
3) Political processes only get 'personal' and thus result in infighting when there is something to be gained by getting in office.   In this case the Notary incurs a cost, but otherwise can gain nothing by having the role and they can lose it if the fail to do a very specific, unambiguous job.   These elections would not be about the 'future direction of the company'.

The problem that I am attempting to solve is not so much just the 'blocks too close' or 'blocks too far' but the fact that an attacker can use short-term uncertainty regarding the chain to attack the network.  The technical challenge is to reach *irreversible* consensus as quickly as possible with out giving anyone opportunity to steal funds.

The challenge with random selection is that you get random failure. 
The challenge with voting pools is that you can get network splits and have synchronization times.  Also choosing who is allowed in the pool is political.

Lets consider the two primary attacks on a trustee system and find technical solutions to them:

1) Notary selectively blocks certain transactions, but continues to operate.
2) Notary stops producing blocks all together.

In the 2nd case the process is very simple.  Every shareholder votes for one or more backup notaries which may only produce a block if the primary notary fails to produce one for a set period of time (1 hour).  After this point the backup notary takes over.  There can be a robust chain of command based upon votes in the past that can automatically take over.

In the 1st case we have two sub cases:
  1) the notary blocks attempts to vote them out of office.
  2) the notary is performing filtering that is 'politically acceptable' and thus they do not get voted out.

I would argue that case #2 is effectively consent of the governed and the only solution is a hard fork with a new trustee for the minority that are against the politically acceptable filtering.

The result is that we only have to deal with case #1.  A notary that is doing partial filtering and is obstructing the election of a new notary.   We can mitigate this particular case by having N notaries that take turns producing blocks.   In the event that any 1 notary fails to produce a block on their turn, then the remaining notaries can vote out that particular notary after X minutes and the next notary in line will take their place.

The key thing with notaries is that they must be prepared to have servers with very high uptime and redundancy. 

The focus should be on how to perform the handoff in a deterministic manner if the primary notary goes rogue.   


 






Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bytemaster on March 30, 2014, 02:21:00 am
A notary that can do 'front running' would be easily detected by the frequent inclusion of never-before-seen transactions.   If this was observed they would be voted out in short order and the attack reverts to the case of subverting the voting process.

Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 31, 2014, 08:21:01 am
2) The technical elections can be manipulated by the false assumption that large stakes indicate trust.

Any system that doesn't give large balances a proportionally large chance of getting elected will simply encourage large balance holders to split up their balance among multiple addresses.  If everyone does this, the result will be massive waste of blockchain storage.  But if only some people split up their balance, the ones who split up will have an advantage relative to those who don't.

Suppose there are 10,000 honest nodes that control 5 addresses on average.  They are all running for notary, and will perform the function faithfully if called to serve.  They haven't created more addresses because they don't care enough about getting elected notary to study the mechanics and engage in abnormal transaction patterns to optimize their chances of getting elected.  Suppose Eve comes along and decides to run for notary with an intent to abuse the position, e.g. she plans to disappear and black out the network until the timeout expires and a replacement is chosen.  Eve runs for notary with 9,950,000 sock puppet addresses.  If each address has an equal chance of getting elected to be a notary, then Eve has a 99.5% chance of getting elected by virtue of controlling 99.5% of the addresses on the network; the fact that each of those addresses only contains a few satoshi is simply irrelevant.  Worse yet, there is a 99.5% chance that Eve's replacement will be another of her sock puppet addresses, which will itself disappear when elected.  Selecting an address Eve doesn't control has one-half of one percent chance of success per hour; the outage will last 200 hours on average.

The above example shows that the chance of getting elected must be proportional to some scarce resource that is intrinsically hard to create (stake).  I chose coins.  Here are some alternatives which I found less suitable:  CDD is scarce, but unfortunately it also encourages sybils, for reasons I've discussed elsewhere.  Hashpower is scarce, but BitShares has already publicly promised to avoid protocols incorporating a computational arms race.  Real-world identities are the scarce resource used to prevent sybils in real-life democratic elections ("stuffing the ballot box"), but obviously real-world identities cannot be verified by an arbitrary node.

Every shareholder votes for one or more backup notaries which may only produce a block if the primary notary fails to produce one for a set period of time (1 hour).  After this point the backup notary takes over.  There can be a robust chain of command based upon votes in the past that can automatically take over.

If a network split has persisted for an hour, you still have a fork.  If the first N backup notaries are offline, your outage lasts N hours.

I suggested the same timeout mechanism, though I didn't specify a suggested value for the timeout.  Let's call the parameter NOTARY_TIMEOUT = 1 hour.  Both your system and mine protect absolutely against forks caused by splits shorter than NOTARY_TIMEOUT.  Both systems generate forks after NOTARY_TIMEOUT has elapsed and the "wrong" side of the split elects a new notary.  My system has the additional advantage that the small side of "lopsided" splits -- where a large number of online coins end up on the same side -- will slow its block production rate proportionally.  Thus, geographically isolated network problems, e.g. a natural disaster that disconnects a single city but leaves most of the Internet intact, will automatically have good failure behavior as long as the isolated area contains a small number of the total online coins -- regardless of whether NOTARY_TIMEOUT expires before connectivity is restored, or which side of the split the current notary is on.  Also, under my system, only nodes that are online at the time of the election can run, avoiding the problem of backup nodes that are offline.

I'll address more of your objections in the next post.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 31, 2014, 09:10:31 am

Lets consider the two primary attacks on a trustee system and find technical solutions to them:

1) Notary selectively blocks certain transactions, but continues to operate.
2) Notary stops producing blocks all together.

To this I would add: 3) Notary temporarily halts block production, slows block production far beyond the target rate, or introduces extreme variance into block production times.  4) Notary creates a transaction based on early access to the precise content of a block.  5) Notary re-orders the transaction list or otherwise transforms the block in a way that changes its semantics while preserving its validity.

Requiring the notary to frequently be replaced lessens 3).  You could certainly be more proactive about policing the situation.  For example, maybe clients by default should automatically stop voting for a notary if too many recent blocks are further apart than 1.5 times the target period.  Or maybe the fees the notary receives for performing the service are docked.  Although, to enforce this, you would also have to find a way to deal with a notary that backdates the block timestamp...

An alternate solution to 2) and 3) would be to reduce NOTARY_TIMEOUT to be much smaller, e.g. twice the target block period.  This is only an okay solution; reducing NOTARY_TIMEOUT makes forks more of a risk.  So you'd probably want to require multiple confirmations.  This is why I like exchanging ideas; I really didn't envision NOTARY_TIMEOUT as long as an hour, so I just sort-of assumed you always had to worry about forks and use multiple confirmations.

For 4), you correctly note that it's certainly possible to catch habitual violations by statistical analysis:

A notary that can do 'front running' would be easily detected by the frequent inclusion of never-before-seen transactions.   If this was observed they would be voted out in short order and the attack reverts to the case of subverting the voting process.

However, infrequent violations are basically indistinguishable from network hiccups.  Whether this is a serious problem is debatable.  I'm not really perturbed by the idea of the notary occasionally trading for himself at the best bid/ask.  I'm more worried about the possibility that a notary will decide to sell this valuable capability to others, who will then have a financial incentive to vote for him.  My system avoids the problem entirely by requiring all transactions, including the notary's own transactions, to only be eligible for inclusion in a block when they've provably been broadcast to a substantial portion of the network.

The solution to 5) seems obvious, but there's a subtle problem.  (A) Avoid transaction malleability, i.e. any change to a transaction invalidates its signature.  (B) Make the block a deterministic function of the transaction set.  In practice, this means sorting the transactions.  The tricky part is in what the sort key should be.  If you sort by transaction hash, then you inadvertently trigger a computational arms race where everyone searches for a transaction with a small hash.  If you trust the notary to generate a random salt to combine with the transaction hashes, he can instead non-randomly generate a salt that puts his own transaction first.

Here's my solution:  Create a salt by hashing a sorted list of the transaction hashes.  Then the sort key for transaction i is H(tx[ i ].hash + salt).

This makes the salt chaotic -- unpredictably dependent on the entire network's actions, but deterministic so the notary can't change it to a favorable value.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 31, 2014, 10:00:31 am

I had really hoped to stay from political discussion in this thread, but it's now become inevitable, because the two proposals being discussed reflect bytemaster's optimism -- and my cynicism -- about the selection of the notary by a political election process.

Political processes only get 'personal' and thus result in infighting when there is something to be gained by getting in office.   In this case the Notary incurs a cost, but otherwise can gain nothing by having the role and they can lose it if the fail to do a very specific, unambiguous job.   These elections would not be about the 'future direction of the company'.

I'm not convinced that the notary shouldn't be compensated with a cut of the transaction fees.  Someone else proposed on this forum that those rewards should vest over time.  That way, the network can punish a notary that disappears or otherwise behaves badly by taking away their pending earnings.

There is something to be gained by getting in office:  The ability to cause the network NOTARY_TIMEOUT downtime by disappearing.  As I outlined in the previous post, your system also allows the notary to censor transactions, and gives the notary the ability to exactly match the best bid or ask.

we have two sub cases:
  1) the notary blocks attempts to vote them out of office.
  2) the notary is performing filtering that is 'politically acceptable' and thus they do not get voted out.

I would argue that case #2 is effectively consent of the governed and the only solution is a hard fork with a new trustee for the minority that are against the politically acceptable filtering.

I would argue that case #2 is effectively indifference of the governed.  Silence is not consent.

Under your system, censorship happens with a unilateral choice by the notary; a veto requires either a hard fork or an active choice of the majority (and in the latter case, can only be implemented by the indirect means of voting for another notary).

My system is the exact opposite.  Censorship requires a hard fork; the unilateral actions of a notary can't accomplish much.  No active choice is required of the majority (which is just as well, since I figure the majority usually won't be bothered to care enough to vote at all).  These features are far from accidental; the main rationale behind my design is specifically to prevent the notary from being able to censor transactions by removing the notary's ability to decide which transactions are included, and to avoid political elections when technical ones are sufficient to the task.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bytemaster on March 31, 2014, 02:41:56 pm
Have N metronodes that take turns in a deterministic manner.  Have block timestamps be deterministic.

Now all attacks must involve collusion.


Sent from my iPhone using Tapatalk (http://tapatalk.com/m?id=1)
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: stuartcharles on March 31, 2014, 04:35:04 pm
Have N metronodes that take turns in a deterministic manner.  Have block timestamps be deterministic.

Now all attacks must involve collusion.


Sent from my iPhone using Tapatalk (http://tapatalk.com/m?id=1)

Just trying to catch up on this development. I get that if you had 100 or so metronodes scattered around the world then this would still be safe, but am i understanding you correctly that you expect these people to have powerful servers ready and waiting to verify a block when its there turn? And not get paid for doing that?

How about if only the top 1000 nodes by balance were allowed to verify blocks and in order for a block to be verified you would have to have agreement from a randomly chosen second node. That way you have the proof of stake and mining.  It would also be difficult and expensive for an attacker to have both of the randomly picked nodes.

these 1000 or 10000 or whatever number would be paid for verifying the block. They would not want to join a pool as it would mean handing over all of their coins to the pool. Like you said bitcoin is paying a fortune for security. Like this we could pay less, still be secure and there are more interesting ways to make money from bitshares than just speculation and mining.

Forgive me if this has already been suggested i have limited time to try and keep up to date on all the projects i see a future for.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bitcoinerS on March 31, 2014, 07:18:18 pm

I dislike the trustee concept. 

Me too.

Also, I just found this on http://nakamotoinstitute.org/

Quote
I've been working on a new electronic cash system that's fully peer-to-peer, with no trusted third party. Satoshi Nakamoto, 2008
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 31, 2014, 07:34:17 pm
case #1.  A notary that is doing partial filtering and is obstructing the election of a new notary.   We can mitigate this particular case by having N notaries that take turns producing blocks.   In the event that any 1 notary fails to produce a block on their turn, then the remaining notaries can vote out that particular notary after X minutes and the next notary in line will take their place.

The focus should be on how to perform the handoff in a deterministic manner if the primary notary goes rogue.   

The "N alternating notaries" idea is a really good one.  It can solve the problem of a notary disappearing and triggering a horribly long timeout.  With N notaries, one designated as primary, you can have the primary notary expected to produce a block.  But the other notaries can mitigate the damage if the primary disappears with an aggressive timeout, e.g. NOTARY_AWOL_TIMEOUT = 2 minutes.  If a secondary notary hasn't seen the primary notary within NOTARY_AWOL_TIMEOUT, then they broadcast a signed message saying "Notary appears to be AWOL."  Then select the next notary in the rotation order that's online.

You need a little more logic to avoid deadlock or inconsistent state when the primary notary produces a block at about the same time the secondary notaries start broadcasting AWOL messages.  Here are the cases:

Case 1)  A majority see the block.  This is normal operation; the primary is operating as expected.

Case 2)  A majority say the primary is AWOL.  There are two subcases:

Case 2a) Unanimous vote for AWOL.  The primary has disappeared or gotten so slow it missed NOTARY_AWOL_TIMEOUT entirely.

Case 2b) Non-unanimous majority vote for AWOL.  The primary is still online, but it generated a block just before NOTARY_AWOL_TIMEOUT.  The new block wasn't able to propagate to all secondaries in time for NOTARY_AWOL_TIMEOUT.

Case 3)  A quorum exists, but there is currently no majority.  This might happen if a minority of notaries are offline, and the remaining online notaries are split between AWOL votes and non-AWOL votes.

Case 4)  No quorum exists.

Three of these cases are obvious.  Case 1) is normal operation.  In Case 2) you kick the primary.  In Case 4) you're probably on the wrong side of a network split.  You shut down entirely until a quorum is found or manual intervention occurs.  You could select new notaries in Case 4) after a lengthy timeout like NOTARY_TIMEOUT = 1 hour, but this risks a fork if you're on the wrong side of a long-lived network split.  I think Case 4) is rare and serious enough that shutting down to wait for either a quorum or manual intervention might actually be the right thing to do.

Case 3 is the hard one; you don't know whether the offline nodes have seen the block, and you need their input in order to decide which way the vote went.  I think you need to vote again after a timeout in Case 3.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on March 31, 2014, 07:54:26 pm

The key thing with notaries is that they must be prepared to have servers with very high uptime and redundancy. 

If you have multiple notaries, this is unnecessary.  In fact, having multiple notaries and fast recovery from a single notary going offline means that there's really no reason an ordinary node can't serve as notary.

So I propose using a random selection algorithm (Poisson process) to add notaries one at a time, and have the oldest notary's term expire if there are too many.  Thus notary duty is not for some elite users with fast servers and connections to the right people to get into a hard-coded list somewhere, rather it is open to any node, with your chance to be selected proportional to your balance.  (As I've explained previously, both here and elsewhere, not using your balance to determine the weight of your vote makes it easy to game the system by making a large number of addresses with tiny balances.)  You get the benefits of fork protection and predictable block times, but the degree of centralization is actually quite limited.

To alleviate uptime concerns, I propose a five-stage scheme:  Unknown, pending, eligible, secondary, primary.  Unknown nodes are most of the network most of the time.  Pending nodes have been selected by the random selection algorithm as potential notaries, but they have to pass an uptime test by signing every block for UPTIME_TEST_LENGTH = 1 hour.  Eligible nodes have successfully passed the uptime test and are waiting for a "seat" to open up.  Secondary / primary refer to active notaries; primary notary duty rotates every block.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: stuartcharles on March 31, 2014, 08:51:21 pm

The key thing with notaries is that they must be prepared to have servers with very high uptime and redundancy. 

If you have multiple notaries, this is unnecessary.  In fact, having multiple notaries and fast recovery from a single notary going offline means that there's really no reason an ordinary node can't serve as notary.

So I propose using a random selection algorithm (Poisson process) to add notaries one at a time, and have the oldest notary's term expire if there are too many.  Thus notary duty is not for some elite users with fast servers and connections to the right people to get into a hard-coded list somewhere, rather it is open to any node, with your chance to be selected proportional to your balance.  (As I've explained previously, both here and elsewhere, not using your balance to determine the weight of your vote makes it easy to game the system by making a large number of addresses with tiny balances.)  You get the benefits of fork protection and predictable block times, but the degree of centralization is actually quite limited.

To alleviate uptime concerns, I propose a five-stage scheme:  Unknown, pending, eligible, secondary, primary.  Unknown nodes are most of the network most of the time.  Pending nodes have been selected by the random selection algorithm as potential notaries, but they have to pass an uptime test by signing every block for UPTIME_TEST_LENGTH = 1 hour.  Eligible nodes have successfully passed the uptime test and are waiting for a "seat" to open up.  Secondary / primary refer to active notaries; primary notary duty rotates every block.

sounds good, and the reward for keeping your node live is you are entering a lottery for the reward?
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: Stan on March 31, 2014, 10:52:47 pm
Submitted without further comment:

(http://laughingsquid.com/wp-content/uploads/metrognome-20110413-101837.jpg)
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: stuartcharles on April 01, 2014, 09:04:08 am
Submitted without further comment:

(http://laughingsquid.com/wp-content/uploads/metrognome-20110413-101837.jpg)

helpful that Stan, thanks.
Can you also explain how we pick the gnome and how he gets paid?
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: NewMine on April 01, 2014, 10:43:36 am
Submitted without further comment:

(http://laughingsquid.com/wp-content/uploads/metrognome-20110413-101837.jpg)

The metro gnome?
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: betax on April 01, 2014, 02:37:45 pm

The key thing with notaries is that they must be prepared to have servers with very high uptime and redundancy. 

If you have multiple notaries, this is unnecessary.  In fact, having multiple notaries and fast recovery from a single notary going offline means that there's really no reason an ordinary node can't serve as notary.

So I propose using a random selection algorithm (Poisson process) to add notaries one at a time, and have the oldest notary's term expire if there are too many.  Thus notary duty is not for some elite users with fast servers and connections to the right people to get into a hard-coded list somewhere, rather it is open to any node, with your chance to be selected proportional to your balance.  (As I've explained previously, both here and elsewhere, not using your balance to determine the weight of your vote makes it easy to game the system by making a large number of addresses with tiny balances.)  You get the benefits of fork protection and predictable block times, but the degree of centralization is actually quite limited.

To alleviate uptime concerns, I propose a five-stage scheme:  Unknown, pending, eligible, secondary, primary.  Unknown nodes are most of the network most of the time.  Pending nodes have been selected by the random selection algorithm as potential notaries, but they have to pass an uptime test by signing every block for UPTIME_TEST_LENGTH = 1 hour.  Eligible nodes have successfully passed the uptime test and are waiting for a "seat" to open up.  Secondary / primary refer to active notaries; primary notary duty rotates every block.

That is a really good idea, no mining, no centralization.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: cryptosig on April 01, 2014, 09:51:31 pm
Why can't we have a clearing house DAC? The DAC could process all the exchange orders for X without the need for a trustee. If the DAC has an interest in mining and inserting the data for other DACs, but not actually participating in the third party DAC, wont there be less incentive to cheat?

If we have to go with a trustee system, there should be a way so the notary can't cheat. Don't get me wrong the firing should always be an option, if your going with a system like this. You should think about maybe putting parts of the transaction through a one way hash so the data is simi-encrypted. In other words the notary will be less likely to cheat if he doesn't know what money belongs to whom, he should only have enough information to determine whether a transaction is valid from the key signatures hashing with the one way hash.

Additionally every bad notary should have a counter notary, such that the two are completely random and unknown to each other but have to be in agreement about the transaction. There needs to be a mechanism where bad transactions can be stopped before they are included into the blockchain. Firing a notary does not fix the mistake in the blockchain.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 02, 2014, 03:02:02 am
Why can't we have a clearing house DAC? The DAC could process all the exchange orders for X without the need for a trustee.

We started out with one problem:  How a decentralized system can process exchange orders efficiently and irreversibly (no forks).  The clearing house DAC would have to solve this same problem.  All you've done is introduce the additional problem of how to communicate between the clearinghouse and X.

You should think about maybe putting parts of the transaction through a one way hash so the data is simi-encrypted. In other words the notary will be less likely to cheat if he doesn't know what money belongs to whom, he should only have enough information to determine whether a transaction is valid from the key signatures hashing with the one way hash.

The information about what transaction belongs to whom must be public to prevent double spending.  A blockchain can't have secrets; everything has to be public in order to be verified.  And the notary doesn't necessarily care what transaction belongs to whom when front-running.

Additionally every bad notary should have a counter notary, such that the two are completely random and unknown to each other but have to be in agreement about the transaction.

There's no way the network can know that two notaries are "unknown to each other."  What test procedure could you use to determine whether two notaries are known to each other?  Keep in mind anyone can generate new address at any time with a click of a button (and with minimal programming skills you can do it completely automatically).  Choosing notaries randomly -- exactly what I suggested -- means it's unlikely that they will know each other.  Weighting the random selection by balance means that generating new addresses won't help you win more votes, it just causes to lose more money to transaction fees.

There needs to be a mechanism where bad transactions can be stopped before they are included into the blockchain. Firing a notary does not fix the mistake in the blockchain.

This is divided into two parts:  (1) Defining rules that determine whether a transaction is good or bad; (2) Rejecting blocks that violate the rules.  Part (2) is a solved problem:  Honest nodes do not broadcast a transaction that does not follow the rules.  Honest miners/minters/notaries will not include a transaction that does not follow the rules into a block.  If a dishonest miner/minter/notary creates a block containing an invalid transaction, honest nodes will not broadcast the block.  Honest miners/minters/notaries will not create further blocks on the invalid block.  Honest clients will display balances and transactions as if the invalid block or any blocks which follow it did not exist -- indeed an invalid block is usually rejected at a fairly low layer and never makes it anywhere near the client's user interface.

Option (1) is the interesting part of the problem, but you don't really engage with it.  What test can the software perform to determine whether a transaction is one of the "bad transactions" that must be stopped?  "Don't include bad transactions" is not something you can really program.  Rather, you must program something along the lines of "Check whether there is a signature.  Then check whether the signature is valid.  Then check that the money exists.  Then check whether the money belongs to the signer.  If all of the previous checks pass, proceed to the next phase of processing the transaction.  If any checks failed, then the transaction is invalid and should not be processed further."

You have to make a distinction between bad behavior (semantics) and validation (syntax).  Bad behavior is something we want to stop people from doing; validation is a computer program that is designed to detect bad behavior.  For example, spending money that belongs to someone else is bad behavior.  The way Bitcoin prevents spending money that belongs to someone else is by checking whether the transaction's digital signature matches the owner of the coins being spent.

As protocol designers, when considering "bad transactions" or any other type of bad behavior, we should ask ourselves:  (A) What bad behavior do we wish to prevent?  (B) What validation algorithm can detect the bad behavior?  (C) How should honest nodes respond when validation fails (i.e. the bad behavior is detected)?

Validation need not be foolproof; sometimes bad behavior may occur even though validation is designed to prevent it.  For example, if Eve breaks into Alice's computer and steals her wallet file, then Eve can generate a digital signature which passes the validation and spends Alice's money.  Even though validation is not a totally impenetrable line of defense, the resulting system is still good enough at preventing bad behavior to be useful and practical.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: stuartcharles on April 02, 2014, 09:23:40 am
Respect to DrLtc, Bytemaster and the rest of you problem solvers
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 03, 2014, 12:27:12 am

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).
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 03, 2014, 12:28:35 am

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.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 03, 2014, 12:31:11 am

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.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 03, 2014, 01:15:25 am

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).
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 03, 2014, 01:46:50 am

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.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bytemaster on April 03, 2014, 08:35:07 pm
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.   
(http://107.170.30.182/assets/img/marketmaker.png)

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. 
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: NewMine on April 04, 2014, 12:08:27 am
Doesn't a "market order" always take precedence over a "limit order"?

Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bytemaster on April 04, 2014, 02:07:42 am
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.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: NewMine on April 04, 2014, 05:07:51 am
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?
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: bytemaster on April 04, 2014, 07:48:22 am
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. 
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 04, 2014, 11:06:31 pm
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.

Title: Re: drltc's Trustee Technical Discussion Thread
Post by: theoretical on April 04, 2014, 11:29:44 pm

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.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: AsymmetricInformation on July 26, 2014, 09:32:35 pm
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.
Title: Re: drltc's Trustee Technical Discussion Thread
Post by: AsymmetricInformation on July 26, 2014, 10:03:23 pm
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?