search

Consensys / anonymous-zether

A private payment system for Ethereum-based blockchains, with no trusted setup.
Other
295 stars 73 forks source link

Improvement using Binary Search in Utils.readBalance ? #20

Closed ibudisteanu closed 4 years ago

ibudisteanu commented 4 years ago

First of all, awesome work !!

Utils.readBalance is a loop from 0 to MAX_NUMBER in order to find the number that verifies the elliptic curve equation accumulator.eq(gB). Can a binary search be implemented to reduce the time complexity from O(N) down to O( log2 MAX_NUMBER), where is N encoded balance? Instead of using BN with Red, we can calculate the numbers with plain BN. Later we can use binary search to iterate identifying the solution i that satisfies the balance.

Is it possible?

https://github.com/jpmorganchase/anonymous-zether/blob/411c692192d0c0d477a2019e153d08a8df3ad82e/packages/anonymous.js/src/utils/utils.js#L11-L23

benediamond commented 4 years ago

Unfortunately, it's not. Binary search only works when you can evaluate a "comparison" function (i.e., less than or greater than). Yet for the discrete log x in a group exponentiation g^x, it's impossible to determine whether the candidate x is above or below the target value. Actually, if it were possible, then discrete log could be solved in polynomial time.

In any case, this readBalance function is only called when you receive a transfer. Hopefully most transfers shouldn't be too large.

One missing feature which would be nice to have is a "whisper" functionality. If you send me funds, you can whisper to me the value of the payment, so that I don't have to brute-force to learn the value.

Let me know if this makes sense.

ibudisteanu commented 4 years ago

Noted. Thanks for the clarification.