Agenda

  1. How can we split the efforts to write a spec for the solving algorithm in quint. What do we need from Taiga?
  • set up one working group on:
    • quint specs
    • taiga
    • FHE hacking
  1. Collaboration on the solver blockchain as suggested by Shoaib.
  • talk to flashbots/suave about collabs - Davie meets Andrew Miller in Barcelona next week-.
  1. FHE discussion -

Ehud Shapiro
- https://dblp.org/pid/s/EhudYShapiro.html
- https://arxiv.org/pdf/2301.04391.pdf
- https://arxiv.org/pdf/2202.05619v13.pdf

Anoma research and development forum: https://research.anoma.net/ - we should have communications there for the apps we building.

GraphShield approach

  • SSE (searchable symmetric encryption) -
    • SSE allows a data owner to encrypt its data (especially texts) such that the data can be queried given search tokens issued by the data owner, while keeping privacy of both the queries and outsourced data.
    • Usually encrypt inverted vectors or search trees for the special purpose of performing keyword based search. In practice, these generic solutions would incur prohibitively a huge amount computation and communication overhead.
    • Generalised to ‘structured encryption schemes’.
  • MPC based techniques - cubic complexity in number of vertices. (SA: These were the papers we looked at before.)
    • Other similar techniques based on oblivious data structures also have huge comm and runtime complexity.
  • ‘distance oracle’ based constructions
    • return only the approximate distance results without generating the exact path after query, and they cannot explicitly support efficient graph updates.
    • Uses SHE.

Recent techniques →

  • Additively homomorphic encryption (for encrypting graphs) and garbled circuits (for comparing encrypted values - GraphShield ).
    • Graph encrypted as adj-list/matrix. (SA: Couldn’t find exactly how, might already have impls for this)
    • Already applied to Dinic! (i.e. the max-flow algo we use)
    • Only needs additively PHE for the most part.
    • The comparison is done in a ‘secure comparison protocol’ using MPC (GCs).
  • Support dynamic updates without re-encrypting the updated graph or using costly dynamization techniques. (SA: Not a concern for us since we don’t need to ‘update’ our payment graph)
  • Looks like the ‘secure comparison protocol’ is interactive, so we need to figure out if we can use it. → PL: It is indeed interactive, in the context of the secure comparison protocol, the server and the proxy would interact to compare two encrypted values without revealing any information about the values to each other. The server holds the encrypted values and the proxy holds the secret key. The server masks the encrypted values with random numbers and sends them to the proxy. The proxy then evaluates a garbled circuit to compare the masked values and sends the result back to the server. This interaction could be facilitated by the relayers in your blockchain network.
  1. Users: Both individuals and groups can act as users in this context. They would generate query tokens and update tokens for their specific operations. If multiple users want to perform operations across shared graphs, they would need to coordinate to generate the appropriate tokens. This could be facilitated through a smart contract or other on-chain mechanism.
  2. Solvers: Having solvers compute off-chain and then submit the encrypted results on-chain is a good way to reduce the computational load on the blockchain. This is similar to the "server" role in the GraphShield protocol. The users (or the smart contract acting on behalf of the users) can then decrypt the results on-chain when needed.
  3. Relayers: Your idea of having relayers perform the evaluation of garbled circuits for a fee aligns well with the "proxy" role in the GraphShield protocol. The relayers would generate intermediate tokens and send the results of the garbled circuit evaluation back to the solvers or directly to the smart contract.
  4. Validators: Validators can indeed perform standard block production tasks as well as generate zero-knowledge proofs for the operations performed by the solvers and relayers. This would provide an additional layer of security and trust in the system, as users can verify the correctness of the operations without needing to trust the solvers or relayers completely.

This setup would allow you to implement the GraphShield protocol in a decentralized and secure manner on your blockchain network. However, it requires careful management of the communication between the different entities and the security of the smart contract, the solvers, and the relayers.

Risks of Intents & decentralizing solvers with a SUAVE like approach

^ Quoting https://www.paradigm.xyz/2023/06/intents#what-can-go-wrong (I think they nailed it)

  • The blog post also describes some solver centralization related risks.

Some problems with the intent model

  • It is unclear what the solver infra will look like in the Anoma model.

    • Will they be centralized?
    • How will solvers cover op costs?
    • Can they charge fees?
    • Where will this fees be settled?
    • What is the medium of settlement? (How is the medium’s supply managed?)

  • How to guarantee an intent isn’t matched twice? (and other complexities arising from a multi-solver arch)

  • Will intents need ordering?

    • How can intents be revoked/modified?
      • Possible solution (from Chris Goes) - add smart expiry conditions to intents
    • How can intent submission be proved publicly?

  • Heliax believes that DAOs will develop to govern solvers and (AFAICT) doesn't want to build that infra. But the problem with DAOs is that there is a lot of friction in their ops and a centralized solver suffers from the same problems as a centralized L2 sequencer (single point of failure, DoS prone, etc.).

  • How can intents express a dependence on systemic metrics, for e.g. welfare schemes →

    I would like my obligation to be settled iff it is in the best interest of the community.

    • Possible solution (from Chris Goes) - have multiple solvers submit solutions and rank them based on systemic conditions.

See also Solver/Sequencer/TSP decentralization is an orthogonal problem! for why solver decentralization is still a problem even if we choose to use a Blockchain for settlement.

Proposal

  • I therefore believe there is potential for a CoFi blockchain here.
    • A CometBFT IBC enabled blockchain (similar to SUAVE), where users can submit their intents along with intent fees.
    • The blockchain can be shared by all CoFi projects.
  • Solvers will then compete to match these intents and can claim the intent fees by submitting a proof that the intent was fulfilled on another (Anoma?) chain.
  • This way we have solved all the solver problems and we also have a solver blockchain that all (CoFi) projects can share.
  • This also solves token issuance problems because we can now just use the native CoFi chain token.
  • Additionally this blockchain can support Holochain (or any other chain…) IBC integration as well by either being the pegged zone itself or providing shared security to it.
The mapping of SUAVE <> Anoma would look like ->
* user preferences <> intents
* builders/executors <> solvers
* outputs full/partial blocks <> outputs full/partial Anoma transactions

(IMHO, all solvers will converge on the blockchain model I described above, so this is something that has a lot of potential even outside of CoFi.)

Select a repo