search

olalonde / proof-of-liabilities

Proof of Liabilities (PoL) is a scheme designed to let companies that accept monetary deposits from consumers (e.g. Bitcoin exchanges, gambling websites, online Bitcoin wallets, etc.) prove their total amount of deposits (their liabilities) without compromising the privacy of individual users.
http://olalonde.github.io/proof-of-liabilities
MIT License
106 stars 37 forks source link

Non-full binary tree has better account distribution privacy #4

Open gmaxwell opened 10 years ago

gmaxwell commented 10 years ago

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.

olalonde commented 10 years ago

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.

gmaxwell commented 10 years ago

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.