Author Topic: drltc's Trustee Technical Discussion Thread  (Read 8572 times)

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

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.

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline bytemaster


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.   


 






For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline Agent86

  • Sr. Member
  • ****
  • Posts: 471
  • BTSX: agent86
    • View Profile
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"

Offline theoretical

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.
« Last Edit: March 29, 2014, 11:36:11 pm by drltc »
BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk

Offline theoretical


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.
BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk

Offline theoretical


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.
BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk

Offline theoretical


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.
BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk

Offline theoretical


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.
BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk