The challenges of full-stack reasearch: the paper

•

Continuing the tweet hurricane 🌀 on the challenges of taking @aptos on-chain randomness from idea ✅ , to *academic paper* 📜, to production-ready implementation and, finally, to deployment (twitter.com/alinush407/status/1770797569947337099). Let's look at *the paper* part of the journey! 🛣️ 🏍️

It's often much easier to come up with a crypto[graphic] construction 👷 than to prove it secure ✍️. Our weighted PVSS and VUF were no exception... So, @bennypinkas and @sourav1547 worked very hard on a security proof, which gave us extra confidence to eventually deploy.

But proving security is non-trivial ❌ In fact, even *defining* security can get quite hairy 🤔 Just glance at the security definition for a VUF, which is actually a very *simple* one 👇 (cc @capcap_max; "It's very simple!") It's not even complete... there's another page! 😆

For the actual security proof, things become subtle. We first "warm up" by proving security of the single-signer VUF ☕. Then, we tackle the thresholdized VUF. (See 👇, but reading it is not for the faint of heart.) Lastly, we prove the weighted VUF we actually use ✅

Luckily, the reduction for the weighted VUF variant turned out to be _not_ too different from the threshold case 😌 (See diffs in grey 👇 )

In the paper, we must also convince our academic peers 👩‍🏫 🎓 🧑‍🏫 that our approach is the best one when compared to alternatives. (1/2) We first argue that *interactive* wDKGs ❌ do not really work in the PoS setting, which arises in most PoS chains, including @aptos.

Specifically, in an epoch-based BFT protocol, the wDKG would need to happen between the *new* committee members, who are _not even online yet_. An alternative is a non-interactive hand-off from the *old* committee to the *new* committee, but the overheads we got were too high.

Indeed, @sourav1547 investigated such a hand-off based approach in our "Simplified VSS" paper: eprint.iacr.org/2023/1196.pdf See twitter.com/sourav1547/status/1688568306696126464 (Actually, @sourav1547, did that hand-off approach even make it into the paper? 🤭)

(2/2) We then argue that a PVSS-based wDKG for a naively-weighted BLS VUF ❌ is not efficient, because: (a) The (field-element) wDKG would be too expensive (great avenue for future work! 🎓) (b) BLS aggregation is slower than our wVUF due to its linear share size.

For me, the most fun part about writing a paper is carefully writing down algorithms in a precise & complete way (see 👇). This is in service not just to our readers, but also to ourselves when we return to the paper years later & we find things easy-to-understand.

In the end, we drafted the paper 📜 and submitted it: eprint.iacr.org/2024/198 (Currently, we are writing rebuttals, yaaaay! 🥳)

Next, I'll talk about: 1. The implementation of `aptos-dkg`, a PVSS library that can be used to build wDKGs. 1. The randomness implementation in @aptos BFT. 2. Validating our paper's approach by obtaining performance numbers from a *real* system! 👇 (Very rare.) Stay tuned 📡 !