The development roadmap of Waku store protocol incentivization using service credentials

[staheri14]

This meta issue embodies the development roadmap of achieving #99
At a high level, we need to take care of the following main components:

• Game theoretical analysis of the payment flow to make sure that both parties rationally would follow protocol specifications (act honestly) to profit from their interaction
• Core anonymous payment implementation: Proper circuit with the associated zkSNARKs proof generation and verification should be developed and integrated into nwaku so that the payment proof can be generated and consumed.
• Payment contract and on-chain interactions: The other part is to deploy a smart contract and allow querying node to obtain credentials by interacting with the contract. The service provider would be also able to withdraw the fund associated with its service by handing in the obtained credentials.

Milestones

In terms of user stories and milestones, we can proceed as follows. Note that phase1 and 2 can be pursued in parallel.
- Phase1, game-theoretic solid payment flow: This milestone is to study the game theory behind the flow of payment to make sure the two parties have enough at stake / or are incentivized enough to follow the protocol specifications.

• Phase1, Core implementation with mocked on-chain interaction: This phase focuses on the circuit part of the payment. No contract deployment is needed, instead, a list of service credentials is hardcoded with known k and r values (the secrets for credential transfer). A Merkle tree is constructed based on the hardcoded list. The querying peer selects a credential from the hard-coded list and constructs a valid transfer proof and sends it alongside its HistoryQuery. The querier sends one credential per request regardless of the amount of queried data. The payment is done upfront by the querier. The receiver should verify the credential transfer and update the tree (the querying node should also update its tree).
  • An initial game theoretic analysis of the payment protocol. This is to study the game theory behind the flow of payment to make sure the two parties have enough at stake / or are incentivized enough to follow the protocol specifications.
  • Raw RFC
  • zero-kit implementation of the circuits
  • Integration of the corresponding zkSNARKs proof into nim implementation
  • Updating the store protocol to handle the minimal payment model as set out for the phase1
  • Dogfoodin
• Phase2, On-chain payment: Developing the smart contract, having it deployed on a testnet, and replacing the hardcoded list of credentials and Merkle tree with proper calls to the smart contract.
  • Updating the RFC
  • Developing the smart contract
  • Developing necessary code to consume the contract from the nim side
  • Functional test and dogfooding

In terms of task distribution, phase1 would be mainly run by @s1fr0, phase2 by @staheri14, and phase3 by both @staheri14 and @s1fr0. All phases will be done collaboratively by @s1fr0 and @staheri14.
Once we agree on the general roadmap, we can follow up with individual milestone issues.

[staheri14]

@s1fr0 Please let me know your thoughts on the roadmap.

[s1fr0]

Look good in general! My main concern is that Phase2 might require lots of new effort to adapt what already done in Phase1. That is, I would personally spend more time in studying/designing a game-theoretically solid protocol first, rather than risking to implement two potentially different schemes among Phase 1 and 2. Indeed, in my opinion, the most delicate part of Phase 1 probably is the circuit implementation, which would clearly be affected by the incentivization mechanism found and analyzed in Phase2. In other words, the game-theoretic solid proposal & analysis should be the first step, especially to understand the ZK primitives we might require: this is also what I recall we agreed during the offsite.

As it is now, I would swap Phase1 and Phase2 and move raw RFC in the new Phase 1. Of course I'd be more than happy to follow this roadmap if we believe is better.

[staheri14]

Thanks for the comment @s1fr0
As indicated in the issue, the two phases 1 and 2 can be pursued in parallel. Following the last PM call, I had this impression that you are interested in starting experimenting with the existing anonymous payment circuits, and I found it safe as a starting point and given that we can reiterate the design at a later stage (and the game theory can be also studied in parallel).
But, I initially and originally agree with prioritizing the game-theory part first. Though, we need to time-box it as we are now facing a time limit (end of September). We do not have to solve everything at once as long as we have well-defined and well-scoped issues to attack in the future. Note that the adversarial model and incentives may expand, so better that we focus on the most realistic attack scenario when inspecting the game-theory part.

The other aspect is to coordinate the task distribution, please check the current task distribution and let me know your thoughts.

[s1fr0]

The other aspect is to coordinate the task distribution, please check the current task distribution and let me know your thoughts.

Indeed the two phases seems a bit unbalanced in terms of tasks, i.e. phase 1 seems quite heavy given the time constraints you mention. I think we can work together on the RFC & game-theory analysis, while I can definitely take care of the circuit. For the integration, I also believe that it would be faster if there is your support too. since to me it looks like we essentially need to replicate what already done for RLN-RELAY (i.e. add an extra proof to messages) and there you have much more insight in the code-base to reach such goal than me.

[staheri14]

@s1fr0 Sounds good to me, we can certainly distribute the load for phase 2 as well.
I am going to switch the two phases, so from now on, phase 1 is game theory and the second phase is the core implementation.

I believe you had a proposal for the game theory part, is it still in place? would be good if you could please open the issue so that we can start pushing that track further. If you prefer, I can also start with the initial game theory analysis, please let me know.

[staheri14]

Some updates: I merged phase1 and 2 (the game theory part can be a task inside the core implementation milestone).

[oskarth]

I agree that we should try to parallelize efforts where possible. In general, we should err on the side of working incrementally and getting something up and running as soon as possible.

[staheri14]

A couple of design decisions to make before the RFC write-up:
The initial MVP would be focused on a general settlement and shall realize the following system model:

1. Focusing on a basic form of payment via which a requester pays the service fee to the provider
2. Scoping out the anonymity for the initial MVP: neither the requester nor the provider has specific anonymity concerns in mind regarding their payment data e.g., their Ethereum address can be known to the other party
3. The exchange of the service fee preferably should not require direct communication between the two parties. The benefits of this design choice are two-fold: 1) makes the design more flexible 2) This will allow easy integration with the pluggable anonymity solution like Tor, where the payment proof can be encapsulated in a message and sent to the provider.
4. Pricing strategy is out of scope i.e., the same service fee is paid regardless of the size of the historical query
5. The two parties are honest and follow the protocol ( it is a plus if we could protect the protocol against rationale adversaries, but not a hard requirement)

cc: @s1fr0 @oskarth comments, suggestions?
Once we agree on the overall system model and requirements, we can proceed with the specific mechanics of the design.

[s1fr0]

3. The exchange of the service fee preferably should not require direct communication between the two parties. The benefits of this design choice are two-fold: 1) makes the design more flexible 2) This will allow easy integration with the pluggable anonymity solution like Tor, where the payment proof can be encapsulated in a message and sent to the provider.

What do you mean exactly by "should not require direct communication between the two parties"? The store query and response themselves already imply some (sort of) direct communication (or at least, an existing communication channel).

Considering the remaining points 1.,2.,4.,5., the initial MVP seems to boil down to something on the lines of "pay a fixed amount in advance to the public store node's ethereum address to receive a (arbitrary long) store query result" (and modulo 3., the payment receipt could be sent along with the query itself). Is that correct?

I also understand that this initial MVP doesn't address store protocol incentivization (i.e., incentivize store nodes to collect, keep updated and available their data), but defines how the fee is transferred between service requester and provider. In other words, the user seems to have no way to distinguish a "lazy" store node (low resources, poorly connected, etc. - but always behaving honestly as per 5.) from more active/connected ones, unless submits the same query at least twice.

[oskarth]

As a next step, I think it'd be a good idea to compare what we had originally planned with when discussing this multiple times, e.g. recent offsites, pre-Devcon discussions etc, with whatever diff we think is required for the solution to be acceptable. Right now it isn't very clear what we are talking about more concretely.

. In other words, the user seems to have no way to distinguish a "lazy" store node (low resources, poorly connected, etc. - but always behaving honestly as per 5.) from more active/connected ones, unless submits the same query at least twice.

We can separate that part out as a separate milestone. Basically start with honest behavior assumption, then communicate more information like uptime etc, then look into slashing conditions. For initial phase we want to keep it simple. There are also game theoretic reasons you'll likely see long-term cooperation among honest nodes, since it is a repeated and possibly non-finite game.