search

hindley-milner-systems / dapp-ertp-airdrop

0 stars 2 forks source link

proof verification without storing all keys on chain #72

Open tgrecojs opened 2 months ago

tgrecojs commented 2 months ago

this implementation currently relies on merkletree.js to handle the following: construcing the tree, generating proofs for each leaf in the tree, verifying each proof against the root hash.

While merkletree.js gets us to a working solution, verifying proofs with the library's verify function requires us to inject the entire tree into the contract code. @dckc informed me last week that if this injection is done via remotable, then this comes at the cost of potentially significant resources. this issue is meant to figure out whether there is an alternative approach that allows us to sidestep such a resource hit. @dckc let me know if i've misunderstood any of the details.

In addition to the cost of passing a remote object into the contract, merkletree.js' API for a basic merkletree is quite heavy, and it consists of mostly feature we have no use of.

Potential Approaches

linear[bot] commented 2 months ago

LAR-113 alternative approach for proof verification

dckc commented 2 months ago

I suggest refining the title to "proof verification without storing all keys on chain"

dckc commented 2 months ago

In office hours, we talked about how we shoud be able to take a proof such as the one in

https://github.com/hindley-milner-systems/dapp-ertp-airdrop/issues/71#issuecomment-2161481800

and verify it agains the ~128 bit root, without reference to O(n-keys) data.

zmanian commented 1 month ago

I don't think this is correct.

The verify function is stateless. https://github.com/merkletreejs/merkletreejs/blob/13b886e0f02c5b90369e5bf0f539aa3fdc769f8b/src/MerkleTree.ts#L1116-L1177

It should only require the root to be stored in the contract to be called.

tgrecojs commented 1 month ago

I've encountered an issue, described here, which aligns with our use case. The issue outlines a solution involving the instantiation of the Merkletree constructor with an empty array specifically to access the verify function.

Upon recreating this approach, I can confirm that it does indeed work. However, I am encountering the following error when attempting to use this method within the context of our smart contract code:

Error {
    message: 'Cannot find external module "buffer" in package file:///Users/tgreco/merkle-airdrop-resources/dapp-ertp-airdrop/node_modules/merkletreejs/',
}
at: >-
    Object.execute (.../compartment-mapper/src/import-archive.js:61:7)
    require (.../compartment-mapper/src/parse-cjs-shared-export-wrapper.js:135:29)
    eval (eval at <anonymous> (eval at makeEvaluate (file:///Users/tgreco/merkle-airdrop-resources/dapp-ertp-airdrop/node_modules/ses/src/make-evaluate.js:92:27)),
    <anonymous>:7:18)
    Object.execute (.../compartment-mapper/src/parse-pre-cjs.js:40:1)
    require (.../compartment-mapper/src/parse-cjs-shared-export-wrapper.js:135:29)
    eval (eval at <anonymous> (eval at makeEvaluate (file:///Users/tgreco/merkle-airdrop-resources/dapp-ertp-airdrop/node_modules/ses/src/make-evaluate.js:92:27)),
    <anonymous>:7:38)
    Object.execute (.../compartment-mapper/src/parse-pre-cjs.js:40:1)
    eval (.../agoric-basics-contract/src/airdrop/helpers/treeOperations.js:1:124)
    eval (.../agoric-basics-contract/src/airdrop/airdropKitCreator.js:1:549)
    eval (.../agoric-basics-contract/src/airdrop.contract.js:1:109)
    async importBundle (.../import-bundle/src/index.js:57:18)

@dckc are you familiar with dealing with these errors?

tgrecojs commented 1 month ago

In hopes of adding context / confirming my understanding of this issue..

I believe @dckc was making the point that the task at hand is relatively straightforward. Given the directness of the desired behavior, he suggested I reconsider this approach in favor of one that avoids introducing additional dependencies and the potential complications that accompany them.

Am i correct in my interpretation @dckc? 🤔

dckc commented 1 month ago

Here's a diagram of the flow as I see it.

There are indeed 2 signature actions, though only 1 on-chain transaction.

This claim step presumes a couple steps below.

sequenceDiagram

   actor Alice
  box wheat Browser
   participant Keplr_A
   participant UI
  end

   participant CometBFT

  box aqua JSVM
  participant vstorage
  participant swAlice
  participant minter1
  end

    Alice ->> UI: claim tokens
    UI -->> Keplr_A: sign({eligible:agoric123,path})
    Keplr_A -->> Alice: ok to sign?
    Alice -->> Keplr_A: ok. sign.
    Keplr_A -->> UI: {msg:{eligible:agoric123,path}, sig}
    UI -->> Keplr_A: signAndBroadcast({ offerId1, minter1, want: 1tok<br>offerArgs: {eligible:agoric123,path}, sig} })
    Keplr_A -->> Alice: ok to sign?
    Alice -->> Keplr_A: ok. sign.
    Keplr_A -->> swAlice: { offerId1, minter1, want: 1tok<br>offerArgs: {eligible:agoric123,path}, sig} }
    swAlice -->> minter1: { offerId1, minter1, want: 1tok<br>offerArgs: {eligible:agoric123,path}, sig} }
    minter1 -->> minter1: checkSig({eligible:agoric123,path}, sig})
    minter1 -->> minter1: checkProof(merkleRoot, agoric123, path)
    minter1 -->> swAlice: 1tok
    swAlice -->> vstorage: 1tok
    vstorage -->> UI: 1tok

This presumes the contract was started with the merkleRoot. (See specifying recipients for details.)

sequenceDiagram

  title: core eval starts contract with merkleRoot

   participant CometBFT

  box aqua JSVM
  participant vstorage
  participant BLDgov
  end

  create participant minter1
  BLDgov ->> minter1: start(merkleRoot=deadbeef...)
  minter1 -->> vstorage: tok1brand

and it presumes the UI gets the address when Alice connects wallet.

sequenceDiagram

  title: UI gets address when Alice connects wallet

   actor Alice
  box wheat Browser
   participant Keplr_A
   participant UI
  end

     Alice ->> UI: connect wallet
    UI -->> Keplr_A: getAccounts
    Keplr_A -->> UI: agoric123...
dckc commented 3 days ago

Seems like there's more to do here: https://github.com/hindley-milner-systems/dapp-ertp-airdrop/pull/99#discussion_r1741276009

dckc commented 2 days ago

w.r.t. the Aug 2 suggestion to codegen the merkleroot into the contract bundle, we worked out more of the details in today's office hours. Now I/we think it should go in the core eval script, deploy-airdrop.js.

The first step is off-chain. yarn build:deployer builds

$ yarn build:deployer
yarn run v1.22.22
$ rollup -c rollup.config.mjs

...
./src/airdrop.proposal.js → bundles/deploy-airdrop.js...
bundles add: airdrop from ./src/airdrop.contract.js
bundles bundled 193 files in bundle-airdrop.js at 2024-09-04T19:12:17.523Z
...
created bundles/deploy-airdrop.js in 1.7s

Installing the contract bundle remains unchanged; it's permissionless, though there is a per-byte storage fee:

sequenceDiagram

   title: install contract

   actor Dev

  box wheat Browser
   participant Keplr_D
   participant cosgov
  end

   participant CometBFT

  box aqua JSVM
  participant vstorage
  participant bundleStore
  end

   Dev ->> cosgov: bundle-airdrop.json
   Dev ->> cosgov: publish
    cosgov -->> Keplr_D: sign(bundleTx)
    Keplr_D -->> Dev: ok to sign?
    Dev -->> Keplr_D: ok. sign.

   Keplr_D -->> bundleStore: bundle-airdrop.json
   bundleStore -->> vstorage: ok
   cosgov -->> vstorage: query bundles
   vstorage -->> cosgov: bundleID,ok

   note right of CometBFT: no BLDgov action yet

Finally, the merkleRoot goes out in the propoposal to BLD stakers that contains deploy-airdrop.js:

sequenceDiagram

   actor Dev

  box wheat Browser
   participant Keplr_D
   participant cosgov
  end

   participant CometBFT

  box aqua JSVM
  participant CoreEval
  participant Zoe
  end

   Dev ->> cosgov: deploy-airdrop.js<br/> w/merkleRoot, contract bundleID,<br/> deploy-airdrop-permit.json
   Dev ->> cosgov: publish
    cosgov -->> Keplr_D: sign(bundleTx)
    Keplr_D -->> Dev: ok to sign?
    Dev -->> Keplr_D: ok. sign.
   cosgov -->> CometBFT: deploy-airdrop.js w/merkleRoot
   note left of CometBFT: ...votes come in,<br/> proposal carries
   CometBFT -->> CoreEval: deploy-airdrop.js w/merkleRoot
   CoreEval -->> Zoe: startContract(..., { merkleRoot })

cc @Jovonni