search

kayabaNerve / full-chain-membership-proofs

18 stars 1 forks source link

Investigate a more efficient set membership proof in curve trees #51

Open kayabaNerve opened 1 year ago

kayabaNerve commented 1 year ago

We commit to the hashed set in 0.5g/m, and then do set membership in (n-1)g. We could merge these to just 1 if we didn't do set membership of the hashed values, yet the hashed values - the claimed member. The issue is we'd then hash those values, which wouldn't line up with the tree in the slightest.

Ideally, we do get this down to just 1g/m.

kayabaNerve commented 1 year ago

Taking the logarithmic derivative may be possible. Instead of 1.5n - 1, it may be 1n + 1 (0.5 for commit, 0.5 for member - claimed_member commit, 1 to eval). I have yet to review this in the slightest though.