Proof of DOT

[eskimor]

This ticket is about adding a generic sybil resistance functionality to Polkadot to be used permissionlessly by any protocol that might need it. This includes Polkadot native infrastructure, but given its permissionlessness, it can be used by any (p2p) protocol to enhance its resilience.

The idea is not new and rather simple: We use a proof of stake mechanism. With this we can prefer participants with stake over participants without. Acquiring stake becomes expensive very quickly if you want to attack. This mechanism can be added to any protocol in a backwards compatible way: Existing clients would still be served based on best-effort (same as they did before), but in addition, participants can lock up DOT for better quality of service, especially in attack scenarios.

Ingredients

• A pallet providing the locking mechanism: pallet-pod + runtime API
• A runtime API to provide a nice interface for querying
• A library/facade to access this system independently of where the functionality actually lives
• RFC for adding this functionality to a system chain. people chain seems ideal.

pallet-pod

Interface:

Extrinsics

type ProtocolName = BoundedVec<u8, MAX_PROTOCOL_NAME_SIZE>;

struct ProtocolConfiguration {

  /// Number of participants (who will be willing to lock up some DOT) do you expect to 
  /// exist for your protocol. Required deposits will be relatively cheap, if the number of participants stays around that number, but will grow to something larger than the entire DOT supply, once number of participants approach ten times that value.
  /// Ballpark estimate is enough (order of magnitude). E.g. 10, 100, 1000, 10_0000, ...
  /// assert!(expected_participants >= 10 && expected_participants <= MAX_PARTICIPANTS);
  expected_participants: u32,

  /// The period, participants have to wait to get their funds unlocked, after they decided to   
  /// leave. 
  unlock_period: BlockNumber,
}

fn register_protocol(origin, protocol_name: ProtocolName, protocol: ProtocolConfiguration);

Register a new protocol you want to have sybil resiistance for, with a name and an expected number of participants.

origin can be any, including root or a chain. Some fee will be charged and some DOT locked for the lifetime of the registered protocol. The name must be unique.

fn participate(origin, protocol_name, max_lock_amount: Balance, peer_identifier: PeerIdentifier);

Show intent to become a participant in the protocol, by registering some identifier (e.g. your PeerId). You can specify a maximum amount of DOT you are willing to have locked for this. Actual amount locked will be determined based on current occupation.

fn leave(origin, protocol_name,  peer_identifier);

Leave the protocol: Your peer identifier will be removed and you get your funds unlocked after unlock_period blocks.

fn remove_protocol(origin, protocol: ProtocolName);

Remove a protocol and claim back the storage deposit for the protocol. This call will fail if there are still participants in the network. Hence, when registering, you should deal with the possibility that you might never get your storage deposit back. The data stored for a protocol is only the configuration, thus that amount should be small. I believe this is acceptable and provides the benefit that the system is by default decentralized: Anybody can create a protocol, but the resulting system would still be decentralized, as nobody, not even that creator will be able to stop it.

View functions

The pallet will also expose the following functions, which should be exported as a runtime API:

type Participants = BoundedVec<PeerIdentifier, MAX_PARTICIPANTS>;

fn protocol_participants(protocol: ProtocolName) -> Result<Participants>;

MAX_PARTICIPANTS should be constrained in a way, such that this call is feasible. We could use a cursor based accessor function, but given that this is supposed to be called from a runtime API, I don't think this complexity is necessary (For now. we can add that later if we actually have demand for networks that large).

Implementation

Protocol registration will ensure that no other protocol with the same name exists. Then it will store the configuration under the protocol's name.

Participation is more interesting. We need to ensure that the system is not itself DOSable. In particular it must not be possible for an attacker to get honest nodes lose their spot, yet we still have limited capacity. We achieve this by setting a conceptual limit on the number of participants to

limit = 10 * expected_participants

further we set the following:

base_price = 0.1 DOT // (pallet configuration)
step = limit/40 // (pallet configuration)

Then we calculate the deposit we take for the nth participant via:

deposit(n) = base_price * 2^(n/step) // integer arithmetic

Example, at the time of registration there have been already 100 participants registered, assuming limit = 1000, then the deposit for the participate call would be: 0.1 * 2^(100/(1000/40)) = 1.6 DOT

Parameters have been picked such that you can not reach limit, as the amount of DOT, you would need to lock, exceed the entire DOT supply. (Economically bounded)

Cost of censorship attacks are high and in favor of the defender. For doubling the price, the attacker would need to invest step/2 times that doubled price. Trying to bring up the price by a factor of 8, will cost x ( step + 2 step + 4 step). Where x was the current price of the time of the attack. This results in 175 x for the attacker to pay, while the to be censored node will need to pay 8*x. (We assume limit to be 1000 and step size thus 25). For smaller limits the attacker would still need to pay at least the same as the to be censored node.

For each participant we store in a DoubleStorageMap<ProtocolName, PeerIdentifier, Participant> the Participant data:

struct Participant {
  owner: Account,
  locked: Balance,
}

For leaving we will remove the entry in above storage map and note in PendingRemoval storage that the funds may be reclaimed at now + unlocking_period. We either check in on_initialize for accounts that should get their funds back or we add an additional extrinsic for claiming back funds that passed the unlocking period.

Provided Facade

To make all of this easily accessible we need to provide a Rust library with the following entry points:

fn register_protocol(origin, protocol_name: ProtocolName, protocol: ProtocolConfiguration);
fn participate(origin, protocol_name, max_lock_amount: Balance, peer_identifier);
fn leave(origin, protocol_name,  peer_identifier: PeerId);
fn remove_protocol(origin, protocol: ProtocolName);
fn protocol_participants(protocol: ProtocolName) -> Result<Participants>;

So essentially the functionality provided by the pallet. With a few key differences:

• We can use more concrete types. E.g. use an actual PeerId, while in the pallet we will use some BoundedVec to keep it protocol agnostic.
• The calls should just work. The library will discover the Polkadot network on its own with minimal configuration and more importantly will craft extrinsics for the right chain for the user to sign and will also know by itself what chain to query to retrieve protocol participants.

This will allow us to move the functionality around (if necessary), change implementation details and even allows for sharding if that ever became necessary. The Facade would just determine what shard to lookup a given protocol based on the name.

[skunert]

Nice proposal!

I expect that its not super very cheap to fetch information from this facade, so for Peer related info and generally operations that happen often, we would need to cache the list of participants locally for sure.

[burdges]

A pallet providing the locking mechanism: pallet-pod + runtime API

It's a dedicated lock, not an overlapping lock ala restaking? We've typically used overlapping locks ala restaking, but in general this really depends upon what your doing.

I expect that its not super very cheap to fetch information from this facade, so for Peer related info and generally operations that happen often, we would need to cache the list of participants locally for sure.

In the worse case, remove Merkle proofs would not necessarily be more expensive than the local Merkle proofs required by local state accesses, just depends how heavily used. In fact, the remove Merkle proofs could even become cheaper than local ones, assuming the majority of state accesses were remote.

[eskimor]

It must be without overlap. Without an attack the amounts locked will stay low anyway, but if there is one, the economic pressure must go up for maximum effect.

I expect that its not super very cheap to fetch information from this facade, so for Peer related info and generally operations that happen often, we would need to cache the list of participants locally for sure.

Yes. This is one of the reasons for the unlock_period. The idea is you only update once in a while. E.g. once per day/ once per session. Whatever makes sense for the application.