James Aspnes, Shlomi Dolev, and Amit Hendin. Computational obfuscations and random oracles for derandomizing asynchronous consensus. arXiv:2504.04046 [cs.DC].
A method for converting an asynchronous randomized consensus to a deterministic asynchronous consensus is presented. The method uses program computation obfuscation and a random oracle, assuming a computationally bounded scheduler, to overcome the impossibility result of Fischer, Lynch, and Paterson.
Two stages are combined, in the first, a new form of computational program obfuscation implemented by post-quantum cryptographic hash functions is introduced, employing time lock puzzles to imply a computational gap between the consensus participants and the (imaginary adversarial) scheduler. In the second stage, a random oracle is implemented by using a post-quantum cryptographic hash function that allows each process to harvest pseudo-randomization from the (cleartext) program and a (consensus) round (variable) and, in turn, implies the completion of the consensus in the presence of a computationally bounded scheduler.
@misc{AspnesDH2025,
title={Computational obfuscations and random oracles for derandomizing asynchronous consensus},
author={James Aspnes and Shlomi Dolev and Amit Hendin},
year={2025},
eprint={2504.04046},
archivePrefix={arXiv},
primaryClass={cs.DC},
url={https://arxiv.org/abs/2504.04046},
}