-
Notifications
You must be signed in to change notification settings - Fork 2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Identify options for transaction discovery that do not require Θ(#transactions * #wallets) effort. #6756
Comments
The problem of updating note witnesses privately is harder than I first thought. I think that's actually going to be the the most difficult part to scale privately, rather than transaction discovery. A mixnet can solve the transaction discovery problem efficiently, but updating witnesses is harder, for the following reason. In the current protocol, a wallet must know a Merkle path to the note it's trying to spend. Part of that Merkle path is the hash of its note's "sibling", i.e. the note to either its left or its right, depending on where its note is in the tree. A wallet with an updated witness can always bridge the witness to the latest Merkle root efficiently and privately when sets of bridges are published and downloaded by all of the wallets, but the problem lies in updating the witness for the first time, where it's necessary to at least obtain that sibling note's hash. Either (a) the wallet downloads all note commitments, using Θ(#transactions) bandwidth, in which case it can update its note's witness in complete privacy, or (b) the wallet does not download some of the note commitments, in which case the server observing these downloads can be sure that the wallet's note is not a sibling of any of the commitments that weren't downloaded (since if it were a sibling of a not-downloaded note commitment, the wallet wouldn't know the whole Merkle path to its note, and couldn't spend it). Ways around that might be:
|
Requiring Θ(#transactions) effort per wallet to detect transactions is not scalable and needs to be replaced with a new paradigm. The options that I know about for improving asymptotics are:
Close this ticket by summarizing the various approaches that allow transaction detection that are asymptotically better than Θ(#transactions * #wallets); detection keys and TEE-based approaches are not in scope of this ticket since their complexity is still Θ(#transactions * #wallets), even though they may be practical near-term solutions.
A closely related issue is transaction data storage: off-chain out-of-band approaches require some method for wallets to back up their transaction data so that importing a seed into a new wallet will work. Indexable transaction tagging approaches could continue to work with the current paradigm of permanently storing all data on-chain, offering faster detection without necessarily improving on storage costs.
The text was updated successfully, but these errors were encountered: