Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Update the proof of custody construction using inputs from the Khovratovich audit #1378

dankrad opened this issue Aug 24, 2019 · 0 comments


Copy link

@dankrad dankrad commented Aug 24, 2019

Dmitry Khovratovich has completed the audit of our proof of custody construction. The highlights are:

  • He improved the previous best algorithm for key recovery from the Legendre PRF to O(sqrt(p) log p) from O(p log p) previously. He published a paper about it here. This is a nice improvement on the previous algorithms but not very worrying for us as his attack is only very effective for a very large number (O(sqrt(p))) of queries, whereas we expose a tiny number. For a smaller number of queries M, the time complexity resolves to O(p log M/M).
  • He found several problems that make the proof of custody independent from the validator keys by carefully crafting the blocks. This is indeed a problem of the construction I originally suggested, but he suggested a very nice remedy in the form of a polynomial Universal Hash Function that provably fixes this problem and stays very close to the current framework

Audit report:Legendre (7).pdf
Suggested updated construction: legendre_proof_of_custody_uhf.pdf

Also: At Crypto'19, we announced some bounties for breaking the Legendre PRF that can be found here:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet
2 participants
You can’t perform that action at this time.