Non-full binary tree has better account distribution privacy
gmaxwell opened this issue · 2 comments
Perhaps just a note for future development: The binary tree can have any shape you want, there is no need to make it a full binary tree. Changing the shape can improve the privacy of the distribution of account values.
At one extreme using a huffman tree will minimize the information leakage— as close to half the remaining balance will be on each child— but may cause very deep trees. The package-merge algorithm can construct a huffman tree subject to the constraint of a maximum depth, though I'm not aware of a handy JS implementation. Though so long as the verifier doesn't care about the tree shape this is just a server side optimization.
Agreed. I think I commented about this issue when coding (https://github.com/olalonde/blind-solvency-proof/blob/master/lib/bsolp.js#L16). I will read up on huffman trees, sounds interesting.
Privacy can be further increased by having the ability to split large balances into more leafs and randomly placing, at the cost of increasing the proof size. ... not sure if it's worth the complexity... maybe so if there really were some accounts that were much larger than all the others.