Avalanche RANDAO – a construction to minimize RANDAO biasability in the face of large coalitions of validators

My interpretation is that an unbiasable RNG (common coin) is probably very much related to consensus in synchronous, because “revealing” very much means a synchronous broadcast.

From this perspective, it could be that unbiasable RNG for > 50% of bad guys is provably impossible, in a similar way to a synchronous consensus for more than 50% of bad guys.

I posted a longer summary of the zero-knowledge problem on the web 3 forum, but it only really summarizes and corrects my comments here.

Michele Orru suggested replacing the ECDH with some secret sharing scheme because multiplying polynomial evaluations and then reconstructing is equivalent to reconstructing and then multiplying the polynomials, so say a (1,2)-threshold scheme becomes a (2,4)-threshold scheme, etc. We should think about VSS and PVSS to actually do this though because we want both a publicly verifiable curve point output at each layer as well as its scalar as a private output. In the end though, we’d obtain a secret sharing scheme with tiered reveals structured such that any subtree contains a revealer at each level, which sounds believable.