probabilistic payment.md

Simple probabilistic payment channel for LES payments

It is possible to do simple probabilistic one-to-many payments with one condition: the set of potential recipients and their assigned probabilities should be decided when creating the payment contract. This is actually a very good fit for light client incentivization. A client can collect many potential recipients (anyone who provided free service) but cannot really know how a particular server will actually react to receiving payments and whether it is worth paying for over the long term. Starting with very small payments is preferable. A one-to-one channel can limit the amount redeemable at the receiver side but the sender still has to pay transaction costs to build a payment route to every new potential receiver. Therefore it has to expect a high amount of free service from every server before risking the first payment. This could make the bootstrapping process for clients slow and/or expensive. One the other hand the proposed method could build a payment route to many servers with a single transaction. It also makes the client strategy simple because the client always has a weighted set of probably good servers and all it has to do is create a new probabilistic payment (including every good server) every time the last one is expired or exhausted.

The probabilistic method

In this scheme the sender creates the contract. The contract has a deposit, a block number and a committed hash that describes the probablility distribution of potential "winners". The block hash of the given block number will decide the winner (miner bribery is probably not an issue with such small payments). When a client wants to send a cheque to one of the listed servers, it sends a Merkle proof of the server having a chance to win and a cheque for an amount redeemable after the specified block number if the given server actually wins. The expected value of the cheque is the amount multiplied by the chance to win. The expected transaction cost of redeeming the cheque is also multiplied by the chance and therefore can be arbitrarily small. The only drawback is that servers have a randomly fluctuating income but that should also even out because they are receiving payments from many clients and they can redeem a few larger sums instead of a lot of small ones.

The probability tree looks like this:

   srv2   srv3
     \     /
      \   /
       \ /
srv1   hash2
  \     /
   \   /
    \ /
    hash1  srv4
      \     /
       \   /
        \ /
     root hash

Leaves are individual servers, encoded as sha3(keyID + randomSalt) in order to preserve privacy of other servers in the tree. Each child has half of the probabilty of its parent. Individual bits of the block hash random source select the winning branch at each level. The winner can redeem its last cheque by presenting both the cheque and a Merkle proof of its position in the tree to the payment contract. Merkle proofs only need to contain the hash of the "other" branch at each level. For example, a Merkle proof for srv3 would consist of the hashes of srv4, srv1 and srv2 and the full encoding (keyID and randomSalt) of srv3.

Further improvement

Instead of giving the server a fixed chance to win and an increasing amount of potential winnings with each new incremental cheque, it is also possible to have a fixed amount of winnings (the entire deposit) and an increasing chance to win. Just like above, the pre-committed tree assigns a potentially winning block hash range for each server (for example, srv3 can win if the block hash is between 0x6000... and 0x7fff...). Now the client could write cheques that allow a certain part of that hash range to win instead of increasing the redeemable amount. When the winning hash is revealed the winner has to present both the Merkle proof of the assigned hash range and the cheque allowing the particular hash to win. For example, if the client writes a cheque for the hash 0x6004... then the server wins the entire deposit if the winning block hash is between 0x6000... and 0x6004... (an 1/2048 chance to win). If the winning hash was not spent by the client then the client keeps the deposit and can either reclaim it or update it with a new root hash and winning block number.

The advantage of this version is the linearity of expected value. With the previous version, if claiming the winnings costs 2 cents and the server has a 1/20 chance to win then there is still a small expected transaction cost (0.1 cents) that is independent from the cheque amount which makes the expected net value of cheques non-linear and uncertain at the beginning (which we really want to avoid). In the new version the expected transaction cost of claiming the winnings is proportional to the cheque amount, the real transaction cost only occurs when cashing the whole deposit (so their ratio can be known in advance). This means that now we can literally pay an arbitrarily low amount to anyone. I guess the price of a minute of minimal capacity connection will be somewhere around 0.001-0.002 cents. Now we can really just pay for a few minutes after receiving a similar amount of free service and basically have an incentivized client up and running in 10-20 minutes, without any prior knowledge about servers. With the previous version the same thing would take several hours, maybe even days.

Even more improvement

Another thing we could change is that the Merkle tree branches do not necessarily have to mean an 1/2-1/2 chance split. Every internal node could include a "split hash" that divides the allowed hash range between the left and right branches. This is a bit of extra complexity in the contract but the code creating the Merkle tree will be simpler because we do not have to use 1/2^N allowances for each server. Another advantage is that it is more efficient, if the client can control the payment allowances according to its estimates more precisely then fewer contracts need to be created. Probably the difference is not so big though so I am fine with leaving this improvement for later or not doing it at all.

I do not quite understand the usage of randomSalt.

So when the sender creates a cheque with a set of servers specified, the sender can use this cheque to send payment before the reveal.
Does it mean in the generated probability tree, the sender will put a random salt inside for each receiver. When the sender sends a cheque off-chain, it will choose a number in the valid range as the salt. So that the receiver will have the probability to calculate the sha3(keyID + randomSalt) correctly?

For example, the used randomSalt for receiver X is 10. So whenever the sender wants to make the payments to X, it has to choose an unused number as the salt. If the range of randomSalt is [0, 100], then it's probabilistic. Do I understand correctly?

But in order to guarantee the salt inside the cheque is indeed random, we need to let both receiver and sender to generate the salt together.

Or we just use randomSalt to preserve privacy?

The randomSalt is just to preserve privacy of other servers and it is up to the client anyway to ensure that. It is not a very critical information, I just wanted to make sure that clients do not by default give away information that is not necessary to give away.