Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

AIP #1: registry: Validator registry by staking ADX #7

Open
Ivshti opened this issue Dec 5, 2018 · 12 comments

Comments

@Ivshti
Copy link
Contributor

commented Dec 5, 2018

Validator registry by staking ADX

Rationale

One of the problems that arises from the way the AdEx works, that is not solved by the core protocol, is how to pick validators.

If you're creating a campaign, ideally you'd pick one validator controlled by you, and one being the publisher platform. You can delegate both validators, but you need to ensure that (1) they will serve opposing interests and (2) that they won't misbehave.

Because of the way the protocol works, if assumption (1) is valid, the only possible misbehavior is going offline. Which is a problem, because the campaign stalls. The funds would eventually be returned, but is still an issue.

An open registry of validators helps mitigate this issue.

Description

A blockchain-based (smart contract or parachain) registry of validators, where the rank is determined of the amount of ADX staked. You need to stake a minimum of MIN_STAKE to be registered.

If you misbehave as a validator, you lose a portion of the stake, possibly related to the amount of funds in the campaign (although that would need price oracles), or related to a specific parameter in the campaign description (allowing larger/stricter campaigns to penalize more).

Proving unavailability

To prove unavailability, a prover (any actor) will submit a commited to OUTPACE state (NewState+ApproveState messages from >=2/3 validators), and a NewState(x) for which x is a state that is a valid transition from the previous one.

Then, there would be a CHALLENGE_TIME period during which the allegedly offline validator can provide their ApproveState to prove that they're online.

We need to think about alternative ways of proving unavailability, since this only works for proving that a follower is unavailable. Alternatively, if we change the way it works naively, it might be vulnerable to tricking the leader into signing states that are valid but pay to the attacker.

Another mitigation could be to simply limit the registry to publisher-side platforms, who are usually going to be followers.

Other slashing conditions

Another slashing condition that we may want to explore is proving that both validators signed an invalid state transition. This means that assumption #1 (two validators act in opposite interests) is broken.

We can also introduce "time proofs": including the latest hash of a specific blockchain (e.g. ethereum) in the signed state. That way, we can prove a certain thing occured no earlier than that point.

Handshakes

After a validator is chosen from the registry, their availability has to be negotiated. A handshake protocol has to be designed, to ensure that validators have the capacity to accept a new channel (campaign).

This is different from Init/Heartbeat messages, which serve another purpose.

Nomination

Any ADX holders can nominate certain validators, therefore increasing their visibility and earning from their fees. The nominators will be slashed proportionally in case the validator itself is slashed.

Implementation

Unlike OUTPACE, which requires a small number of blockchain transactions, the registry might need high throughput or at least should be able to sustain high throughput.

Furthermore, the registry has a lot to benefit from on-chain governance and easy upgradability. Therefore, we think that the registry should be implemented on Substrate and should eventually run on Polkadot, as those solutions are very suitable for this particular usecase.

Availability

Since this system slashes validators for becoming unavailable, concerns like "what happens if my network connection dies" are absolutely valid.

The system should be designed to only slash unavailability longer than a few minutes, and most network outages on most cloud services do not last longer than that.

However, if you're staking large sums, you'd still want to ensure you don't get slashed just because of a technical failure.

This is why it's important to note that being a single validator does not imply you only have one server or you're located in one data center - you can run a validator in a distributed way, across a number of data centers/servers, in order to ensure redundancy.

Having an in-protocol distinction between types of unavailability (malicious or technical failure) is not only next to impossible, but also goes against what we're trying to ensure. Ultimately, whoever nominated the validator would expect availability, no matter what.

Ranking

validators will be ranked by the formula: valueOf(totalStakedADX) / sum(valueOf(channel.deposit) for channel in channels)

if you're appointing 2 validators for your campaign (not using your own node), then:

  • if the result of this formula is lower than a certain threshold (e.g. 3), using this validator in your campaign should be considered ill-advised
  • if the result is <1, the validator is certainly dangerous, as they may form a cartel with the other one and steal all deposits

UI: there should be a clear visual representation of this ranking coefficient in the UI, so that users are aware of potential risks

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 6, 2018

it can work for advertiser-side platforms too; if the advertiser is not satisfied with the platform (e.g. it's unavailable), they can launch an ongoing challenge where:

  • they submit a base agreed-upon state and request
  • this base agreed-upon state can be updated (by anyone as long as they submit a valid state), therefore extending the challenge period
  • the challenge can be killed altogether by the advertiser-side platform allowing the advertiser to exit with the rest of their funds (signing a new state which exhausts the channel)
  • if the period expires, the ASP get slashed and possibly some (or all) of the funds go to the advertiser as a compensation
@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 6, 2018

both challenge games should allow updating the base agreed upon state

otherwise, it's possible to use a challenge state NewState which is a valid transition from an older state but not a valid transition from the latest

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 10, 2018

We need to think about throughput. The larger your stake, the higher you will be ranked, increasing the chance you'd be picked. This means you have to be able to handle more throughput, or else you'll be slashed for unavailability. In other words, stakers need to be careful not to stake large amounts unless they're ready for large visibility.

Another option is to just add a second stage of filtering everywhere the registry is used, which will simply ask the validators whether they have the capacity to take new channels. This might be flawed though - as how the throughput is balanced between the system should also depend on stake.

@ameensol

This comment has been minimized.

Copy link

commented Dec 13, 2018

Difficulty of properly slashing

To prove unavailability, a prover (any actor) will submit a commited to OUTPACE state (NewState+ApproveState messages from >=2/3 validators), and a NewState(x) for which x is a state that is a valid transition from the previous one.

Then, there would be a CHALLENGE_TIME period during which the allegedly offline validator can provide their ApproveState to prove that they're online.

The main issue I see with this strategy is that a validator could be unresponsive to OUTPACE updates and yet still respond to challenges onchain, thus reducing the throughput of the advertising campaign to block times, but still avoiding being slashed.

If this were to happen in an obvious way, (e.g. the validator ignores all OUTPACE updates), then I would assume the publisher and advertiser would agree to drop them and to pick a different validator, then continue their business. However, the validator could also grief the publisher and advertisers by ignoring OUTPACE updates every so often, in which case it might take longer for them to get dropped. This could be solved by requiring the validator to agree to a certain SLA in advance, so the publisher and advertiser know exactly when to move on.

But because the validator misbehavior as described above will only get them dropped as a validator, but not have their stake slashed, it would be relatively inexpensive to conduct. A motivated third party who wanted to grief the AdEx ecosystem could stake a lot of ADX across various accounts, become the validator for many campaigns, and periodically force each of them to chain by ignoring their state updates (though the value may drop).

Competitive considerations

A different issue would be that instead of wanting to pick a validator at random, I may be concerned about data privacy and want to pick a validator who I trust not to leak data to my competitors. In the current paradigm, there is no way to coordinate around this behavior. Even if I were able to prove it in some offchain forum, the best I could hope for is to inspire others to not use the validator in question.

ADX as a Governance and Dispute Resolution token?

Furthermore, the registry has a lot to benefit from on-chain governance and easy upgradability. Therefore, we feel that the registry should be implemented on Substrate and should eventually run on Polkadot, as those solutions are very suitable for this particular usecase.

You might be able to solve a few of your problems at the same time here. If you plan on using Polkadot and Substrate anyways, it might make sense to allow for OUTPACE to bring general complaints (unavailability, data leaking) to a court-like system to request that a validator be slashed. My guess is that you'll want to coordinate governance (validator dispute resolution, registry upgradability) with staked ADX, and then may even be better off using a stablecoin like DAI for validator staking. This way the incentives for a validator to misbehave don't increase if the price of ADX drops.

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 13, 2018

In reverse order:

Re governance/dispute resolution: ultimately, this will get down to the classic on-chain gov vs off-chain gov debate; I am very excited about exploring the possibilities, but IMO core protocol must be up and running first, and we have to see what the problems/disputes are in real life before being close to even designing a good-ish on-chain gov system

The privacy concern is a very good point: there's no way (that I can think of) that will solve this. Furthermore, I'd consider it out of the scope of the Registry. I'd imagine that large parties who are concerned about privacy would run their own validators.

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 13, 2018

Re proper slashing

Let's view this in a simple case: there's one leader and one follower.

Leader proves that follower is unavailable

The leader submits the new state on-chain and demands that the follower will sign it within a certain period.

If they don't, they get slashed. If they do, nothing happens.

The way this works in real life is:

  • Follower disappers
  • Leader continues producing new states, but the follower is not approving them
  • Leader launches a challenge
  • If the follower is online, they submit the signed state and everything is fine; this state can now be used by publishers to withdraw, so even if they don't submit it off-chain it's fine
  • if the follower is offline, they get slashed
  • If the follower is online on-chain, but offline off-chain: doesn't matter; the leader advances the state with all of the impressions counted, and the follower can either sign and submit on-chain therefore producing a message that can be used to withdraw (together with the leader's msg), or not do so and get slashed

One might think that a problem with this is that the leader can effectively force the follower into signing a new state. However, they can't force them into signing an invalid state transition (since this is checked on-chain), and by design, the follower always signs new valid state transitions.

If the leader is the one misbehaving, read on...

Follower proves that leader is unavailable

This one is much more complicated. The only game theoretically sound way that I thought of is this:

  • Follower submits last approved upon state (with msgs from both validators)
  • Any party can submit a newer one (if it's agreed upon by every validator and a valid state transition), within a certain timeframe; each submission increases the total challenge timeout
  • Submitting an approved upon state where the channel is exhasuted (entire deposit is distributed) ends the challenge

The way this will work in real life is:

  • Leader disappears
  • Follower launches the challenge
  • if the leader is online, everything will be ok
  • if they are not, they will get slashed
  • if they are online on-chain but offline off-chain, they are dooming themselves into signing and submitting new states until the channel is exhausted

This is a bit like counterfactual channels.
Whatever is happening off-chain, will be replicated on-chain in the case of a dispute.

However, indeed, this is not a large enough punishment for effectively stalling the campaign (@ameensol dothis is practically the issue you're referring too). A possible solution would be requiring that the challenge is exhausted within the channel validUntil date (even if funds are not distributed to publishers, they can still be turned to the advertiser). Needs more though though.

Another problem with this is that the follower might force the leader into spending gas/tx fees. Will think more on this

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 17, 2018

Another thing to explore, but is more complicated, is making mechanisms for (1) ensuring the chosen validators have opposing interests and (2) if they do form a coalition, there should be a way to punish them

one way to do this might be to make one validator be able to punish the other, should the other try to bribe them
cc @decanus

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Dec 17, 2018

A potential way to fix the "follower proves that leader is unavailable" is by combining this challenge with a request to close the campaign

The request to close the campaign pays a significant fee to the leader, so it's in the leader's interest to allow it ASAP and move on to other campaigns.

Furthermore, the challenge time could be significantly reduce, as we'd use a "timeout to close the campaign" rather than "channel timeout"

This puts the user at a slight disadvantage though, as irresponsible leaders can get away from getting punished by simply allowing users to close their campaign and pay them out.

@decanus

This comment has been minimized.

Copy link
Collaborator

commented Dec 21, 2018

one way to do this might be to make one validator be able to punish the other, should the other try to bribe them

The problem with these games is sufficient evidence and how to present such evidence and who then votes on said evidence.

@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Jan 4, 2019

Back to offline penalties

regarding section "Follower proves that leader is unavailable" and "if they are online on-chain but offline off-chain, they are dooming themselves into signing and submitting new states until the channel is exhausted"

This is very similar to producing empty blocks in Bitcoin/Ethereum - it's (kind of) expensive, you gain nothing from it, but it's a legitimate and functional attack that would stall the network, without a way to be punished for it.

The best way to mitigate (although as we've seen, not bullet proof) is to meter validator fees by processed events, so that you'd be losing out on validator fees. Again, needs more thought.

see AdExNetwork/adex-validator#15

@Ivshti Ivshti changed the title Validator registry by staking ADX registry: Validator registry by staking ADX Feb 9, 2019
@Ivshti Ivshti pinned this issue Mar 19, 2019
@Ivshti

This comment has been minimized.

Copy link
Contributor Author

commented Apr 25, 2019

additionally, this Registry needs to cover double-signing in the future in case we use more than 2 validators

@Dylanoshi

This comment has been minimized.

Copy link
Contributor

commented Apr 29, 2019

In reverse order:

Re governance/dispute resolution: ultimately, this will get down to the classic on-chain gov vs off-chain gov debate; I am very excited about exploring the possibilities, but IMO core protocol must be up and running first, and we have to see what the problems/disputes are in real life before being close to even designing a good-ish on-chain gov system

The privacy concern is a very good point: there's no way (that I can think of) that will solve this. Furthermore, I'd consider it out of the scope of the Registry. I'd imagine that large parties who are concerned about privacy would run their own validators.

**^this would fit in with having groups of publishers running their own markets, no?

@Ivshti Ivshti changed the title registry: Validator registry by staking ADX AIP #1: registry: Validator registry by staking ADX May 28, 2019
@Ivshti Ivshti self-assigned this Aug 16, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.