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

0 Members and 1 Guest are viewing this topic.

Offline theoretical

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.
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 cryptosig

  • Jr. Member
  • **
  • Posts: 25
    • View Profile
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.
« Last Edit: April 01, 2014, 10:07:27 pm by cryptosig »
BTSX: wallet_approve_delegate cryptosig
KEYID: wallet_approve_delegate delegate-cryptosig

Offline betax

  • Hero Member
  • *****
  • Posts: 808
    • View Profile

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.
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline NewMine

  • Hero Member
  • *****
  • Posts: 552
    • View Profile

Offline stuartcharles

  • Sr. Member
  • ****
  • Posts: 281
    • View Profile
Submitted without further comment:



helpful that Stan, thanks.
Can you also explain how we pick the gnome and how he gets paid?
« Last Edit: April 01, 2014, 09:06:45 am by stuartcharles »

Offline Stan

  • Hero Member
  • *****
  • Posts: 2908
  • You need to think BIGGER, Pinky...
    • View Profile
    • Cryptonomex
  • BitShares: Stan
Submitted without further comment:

Anything said on these forums does not constitute an intent to create a legal obligation or contract of any kind.   These are merely my opinions which I reserve the right to change at any time.

Offline stuartcharles

  • Sr. Member
  • ****
  • Posts: 281
    • View Profile

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?

Offline theoretical


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.
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

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.
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 bitcoinerS

  • Hero Member
  • *****
  • Posts: 592
    • View Profile

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
>>> approve bitcoiners

Offline stuartcharles

  • Sr. Member
  • ****
  • Posts: 281
    • View Profile
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

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.

Offline bytemaster

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
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 theoretical


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.
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


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.
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

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.
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