I’m intrigued by the notes discovery problem and have been exploring solutions with a focus on user autonomy and the elimination of third-party involvement.
If considering the use of tags, the perfect solution would be aggregatable tags. Then it would allow the user to just check the aggregated tag for the block or even an epoch (or even ask the rollup contract to calculate such a tag for a custom period). That’s an idea I came up with after researching KZG commitments.
I imagine the whole flow the following way:
The user generates transactions with tags based on the receiver’s public key.
The validator takes a batch of transactions and aggregates all the tags.
Then each user’s wallet could check if the user was tagged by dividing the aggregated commitment with a public key.
After the user had discovered the tag presence, he could keep investigating for the transaction itself.
Using the methods used in KZG it’s possible to build a polynomial that would pass through the points on the elliptic curve that represent a set of tags (the piece of data that would tell the user that this transaction is meant for him).
Then, probably the user could check if his public key is in this set with the way it is done in KZG. A clear indication to the user would be the fact that p(xpublic_key) = ypublic_key, which could also be presented as (p(x) - ypublic_key) / (x - xpublic_key) = q(x). My main concern is that the scheme describes membership or non-membership proof, which implies explicit proof generation, while here we need something more like membership or non-membership check. The succinctness of the scheme is achieved partly due to the fact that we know the witness polynomial and can evaluate it in the needed point.
I also do not exclude the possibility that I might be moving in the wrong direction in my research (despite my feeling which is the opposite), that’s why I’m looking for support and feedback from the community.
Thanks for the contribution. It’s an interesting suggestion and worth further discussion.
In particular, I wonder if it is something that can be combined with other schemes to reduce the amount of work a user has to do overall to retrieve their notes.
Hi @VictoriaGrasshopper,
Great to see you’re interested in the problem. So I went through your idea and I have a couple of comments. To aggregate n tags by interpolating them as a polynomial you’ll end up with a polynomial of degree n-1. Now you can either have a polynomial as its n coefficients or some other representation (point value representation for instance).
Now if we were to keep this polynomial as the aggregate tag, this would lead to the recipient needing to download n field elements (quite similar to downloading the n tags), and then evaluating this polynomial or computing the quotient as done in KZG would require \Tilde{O}(n) operations. So if the whole polynomial is used as an aggregation this would lead to this not being better than just keeping a list of all the tags and checking whether your tag is in that list by iterating through all of them.
How this is done in KZG is that the verifier does not do this work but delegates this task to a prover which convinces the verifier they did this correctly. So for the idea to make sense, you would require a third party to prove that your element was in the aggregated set. Now there are two issues with this. First, if done naively you have to reveal to the third party which tags you’re looking for, which would allow the third party to check which notes belong to you. Second, this would pretty much be using a polynomial commitment (KZG in this case) as an accumulator (or a vector commitment). For instance, you could do the same with a Merkle tree, i.e. the root of the Merkle tree is your aggregate tag and you do a Merkle membership proof.
I believe you were hoping that using something similar to KZG you could do a membership check instead of a membership proof. However, assuming tags are relatively random, you would soon end up facing information-theoretic lower bounds for this task, i.e. leading to solutions such as bloom filters.
Thank you for your message and especially for your time!
Yeah, you got that right, and everything you described makes sense. I had a feeling that this idea was idealistic rather than realistic. Your message was absolutely helpful for me on the way to deeper understanding of KZG