j-berman full-time development (3 months)

What

Work full-time 3 months on:

• Integrating full-chain membership proofs++ into Monero under RingCT.
  • As part of this CCS, I will prioritize and guarantee completion of the following in this PR: https://github.com/monero-project/monero/pull/9436
    1. Trim the tree on reorgs and when popping blocks.
    2. Key image migration.
    3. Optimize tree building where possible.
       • Multithreaded output conversion to leaves.
       • Multithreaded hashing.
       • Batched inversion.
    4. Construct fcmp++ transactions.
       • I anticipate updating cryptonote::construct_tx_and_get_tx_key for this, and not touching wallet2 in this proposal.
       • By the end of this proposal, there will be a modular function wallets can use to construct fcmp++ txs, but I may not have an end-to-end functioning wallet that can construct fcmp++ txs implemented by the end of this proposal.
    5. Verify fcmp++ transactions.
    6. Consensus changes for fcmp++.
       • New unlock time logic.
       • Allowing new fcmp++ RCT type.
       • Implement a grace period for current tx types in the pool at the fork to make it into the chain.
       • Misc. necessary changes.
  • Work together with @dangerousfreedom on full wallet scanning.
  • The remaining integration tasks that I would also work on if time permits and someone else doesn't:
    • Construct fcmp++ transactions in a fully functional wallet.
      • Pre-requisites: modular function to construct fcmp++ transactions and full wallet scanning.
    • Implement the RPC route for light wallets to query for paths in the curve trees tree.
    • Wallet changes for background syncing.
    • Multisig.
• Continuing Seraphis wallet library work.
  • Making it clear up front: I anticipate not making much progress on the Seraphis wallet library work in this CCS. I plan to prioritize fcmp++. If time permits, I would work on bringing the Seraphis wallet library to production.
  • To be clear, working on the Seraphis wallet library is not implementing the Seraphis upgrade; it is bringing the Seraphis wallet library, which supports scanning today's blockchain, into the core Monero repository. This would speed up wallet scanning today, and is part of an effort to deprecate wallet2 and its technical debt, and replace it with the Seraphis lib (source).
  • Next I plan to resolve merge conflicts in the current open PR's, and open all piecemeal PR's to the core Monero release branch to prepare Monero daemons/wallets and reduce the size and scope of the async scanner PR.
• Misc. review, debugging, etc.

Who

j-berman on github / jberman on matrix / IRC

Past CCS's:

• https://ccs.getmonero.org/proposals/j-berman-3months-full-time-7.html
• https://ccs.getmonero.org/proposals/j-berman-3months-full-time-6.html
• https://ccs.getmonero.org/proposals/j-berman-3months-full-time-5.html
• https://ccs.getmonero.org/proposals/j-berman-3months-full-time-4.html
• https://ccs.getmonero.org/proposals/j-berman-3months-full-time-3.html
• https://ccs.getmonero.org/proposals/j-berman-3months-full-time-2.html
• https://ccs.getmonero.org/proposals/j-berman-3-months-full-time.html

Proposal

317 XMR

480 hours, 0.25 XMR/hr + $65/hr, $158/XMR from coingecko

mentioned in commit b5f7d3d2

merged

I have sent 105.67 XMR from the General Fund to this proposal in tx 1e611b97733367da9e9fc2fa4269851c13f029aea7022614c9791c2f604dbae5.

Update 1

195 hours

Completed:

1. Trimming the tree on reorg/pop blocks.
   • All tests now passing.
2. Key image migration.
3. Optimized tree building:
   • Multithreaded output conversion to leaves.
   • Multithreaded hashing.
   • Batched inversion.
   • Technically there is still some room for optimization, but continuing to squeeze feels like premature optimization at this stage. My view is that we can revisit continued optimization on tree building once we have actual sync perf figures.

I'm currently waiting on @kayabaNerve to complete work on the prove/verify API before I continue on to construct/verify/make consensus changes for fcmp++ txs (deliverables 4/5/6 of this CCS). To maintain forward progress on the fcmp++ integration, and since dangerousfreedom is taking a hiatus from working on Monero, after discussing in the #No-Wallet-Left-Behind channel, I decided to take on full wallet scanning for fcmp++.

Full wallet scanning overview: fcmp++ works by proving you own an output (or "enote") within a special tree called a curve tree. All valid and spendable outputs across the entire chain compose the leaves of the tree. When constructing the "full-chain membership proof", the user proves their output is a member of the tree, without revealing which output it is. To construct the proof, a wallet needs the output's path in the tree (from leaf to root) at the latest block. Keep in mind the state of the tree changes every block, so an output's complete path in the tree changes every block as well. Full wallets must keep track of the wallet's received outputs' changing paths while syncing.

What I've done so far:

• Set up a new interface and derived class that full wallets will be able to use to sync the tree.
• The class internally handles updating received output paths in memory while syncing.
• It handles correcting paths on reorg as well.
• It will be reusable in both wallet2 and the Seraphis lib scanner.
• As @jeffro256 proposed, I implemented an interface, then implemented a derived class that stores registered output paths / tree data in memory. This way a different class implementing the interface could use a db instead (e.g. a multi-wallet sync impl might want to do this).
• I'm working on wallet sync in this branch here: https://github.com/j-berman/monero/commits/fcmp%2B%2B-tree-sync/
• Here is a direct link to the latest commit containing the interface, which also includes fairly detailed comments on how it's expected to work: https://github.com/j-berman/monero/blob/b206d4390762898a9d6eeb03923d10034a7a9ebb/src/fcmp_pp/tree_sync.h#L44-L92
  • Here is the implementation of the derived class that wallet2/Seraphis lib can use to sync the tree: https://github.com/j-berman/monero/blob/b206d4390762898a9d6eeb03923d10034a7a9ebb/src/fcmp_pp/tree_sync_memory.h#L98-L154
• I've written some solid unit tests here: https://github.com/j-berman/monero/blob/b206d4390762898a9d6eeb03923d10034a7a9ebb/tests/unit_tests/tree_sync_memory.cpp

Next major steps:

• Integrate this class into wallet2.
• Enable starting to sync the tree from a wallet's arbitrary restore height, rather than require sync from genesis.
  • This requires an RPC route to get the right-most edge in the tree at a given height.
• More tests.

Update 2

379 hours

• Implemented building the tree for fcmp++ in wallet2.
  • By building the tree locally in wallet2 when syncing the chain, the wallet will be able to construct the fcmp++ proof without leaking relevant data to a daemon which output (enote) a wallet is spending.
  • Source: https://github.com/j-berman/monero/tree/fcmp%2B%2B-tree-sync-dev
  • On my machine, it's currently 2-2.5x slower to sync a wallet from genesis now using a local daemon (compared to syncing a v0.18.3.4 wallet).
  • The initial implementation was 5-6x slower to sync -- I put in a solid amount of effort getting it down to where it is now.
  • It's possible that tree building will not slow down production sync time in wallet2 with further optimizations to 1) checking outputs for torsion, and 2) arithmetic on the Helios and Selene curves.
    • Scanning outputs (enotes) to see which belong to the user would remain the bottleneck sync time when using a local daemon.
  • The primary speed-up I implemented was building the tree in parallel to identifying receives.
    • Secondarily the implementation now extends the tree with a chunk of blocks at once, rather than extend the tree 1 block at a time.
  • Worth noting: there is still room to optimize the tree sync design further to get CPU utilization to 100%; however, I believe it will be much easier to do so when integrating tree sync in the Seraphis lib async scanner.
    • Further optimization at this time seems premature.
  • Another major speed-up was a 6x improvement in constructing commitments for transparent amounts.
    • This change was suggested by @kayabaNerve.
    • Source: https://github.com/j-berman/monero/commit/3db1aa15f62eb6d1e66de22881e01393112bcdbb
      • The source includes benchmarks in /tests/performance_tests/zero_commit.h.
    • Note: the daemon currently relies on this function to sync, so this improvement can be used to speed up sync today (source).
• Fixed the migration code to resize the db as needed.
  • Source: https://github.com/j-berman/monero/commit/f44e7f53ae9398e2bf5e3825e304365c6910b9a1
  • The migration would halt sporadically before this change.
• Submitted a PR for a test framework for wallet cpp <> live daemon tests.
  • Source: https://github.com/monero-project/monero/pull/9547
  • This was initially part of the Seraphis lib async scanner and I figured it would be helpful for @SNeedlewoods.
• Rebased piecemeal PR's from the Seraphis lib async scanner.
  • https://github.com/monero-project/monero/pull/9380
  • https://github.com/monero-project/monero/pull/9381

Goals for the remainder of the CCS

• Enable starting to build the tree from a wallet's arbitrary restore height, rather than require sync from genesis.
  • I laid out the requirements here: https://github.com/j-berman/monero/blob/5dae7d721a6d1bc0b586efb9005100288c9e0adb/src/fcmp_pp/tree_sync.h#L75-L83

Stretch goal (that I may not be able to complete before the end of the CCS)

• Construct the fcmp++ proof with an output's synced path in the tree.

Update 3

483 hours

FCMP++ wallet tree sync (via building the tree locally) is set up and integrated into wallet2.

• Source: https://github.com/j-berman/monero/commits/fcmp%2B%2B-tree-sync-dev/
• Completed the task to start sync from arbitrary restore height N.
  • Implemented an extension to the /getblocks.bin RPC route to get init data needed to start syncing the tree from an arbitrary height N.
    • Source: https://github.com/j-berman/monero/blob/3d0aff7a24edb759db29e7d088daecd6a9fb1731/src/rpc/core_rpc_server.cpp#L613-L685
  • Implemented a new db table that keeps track of custom timelocked outputs by their last locked block idx.
    • Source: https://github.com/j-berman/monero/blob/3d0aff7a24edb759db29e7d088daecd6a9fb1731/src/blockchain_db/lmdb/db_lmdb.cpp#L2554-L2657
    • Implemented the migration of custom timelocked outputs into this new table.
      • Source: https://github.com/j-berman/monero/blob/3d0aff7a24edb759db29e7d088daecd6a9fb1731/src/blockchain_db/lmdb/db_lmdb.cpp#L7515-L7538
  • Implemented a new db function to get recently locked outputs (outputs that are not custom timelocked, but locked as of a given block N).
    • Source: https://github.com/j-berman/monero/blob/3d0aff7a24edb759db29e7d088daecd6a9fb1731/src/blockchain_db/lmdb/db_lmdb.cpp#L2659-L2729
  • Implemented a new db function to get the right-most edge of a tree as of a given block N.
    • Source: https://github.com/j-berman/monero/blob/3d0aff7a24edb759db29e7d088daecd6a9fb1731/src/blockchain_db/lmdb/db_lmdb.cpp#L1580-L1630
  • Implemented the wallet-side algorithm to initialize the tree sync cache with the RPC response data.
    • Source: https://github.com/j-berman/monero/blob/3d0aff7a24edb759db29e7d088daecd6a9fb1731/src/fcmp_pp/tree_sync_memory.cpp#L1300-L1396
• Verified that the implementation builds the same tree as the daemon and correctly maintains a received output's path in the tree while syncing via wallet2.
• Did some cleanup on the implementation.

The above task took up the remaining time of my CCS.

mentioned in issue #150