consensus-specs icon indicating copy to clipboard operation
consensus-specs copied to clipboard

Switch to 64 bit field elements for data availability checks

Open dankrad opened this issue 5 years ago • 2 comments

New CPUs have special instructions that can do 64 bit binary field operations efficiently (the main requirement for this is to have a carryless multiplication). This gets rid of the logarithm lookup tables to compute field multiplications. This benchmark written by @kilic and @saitima shows that this is 4x faster than the 16 bit lookup table approach (it can do a 64 bit operation in the same time it takes to do 16 bit operations using lookup tables)

https://github.com/kilic/gf

This indicates we should switch to 64 bit field elements to improve performance.

dankrad avatar Jul 16 '20 21:07 dankrad

I feel like this decision depends critically on whether we end up using fraud proofs or Kate commitments or STARKs. If we intend to rule out Kate commitments, then it's certainly reasonable.

vbuterin avatar Jul 19 '20 23:07 vbuterin

Hmm, wasn't our current roadmap on this that even if we're going to use Kate for state, it would still be more efficient to do data availability using the old scheme (since Kate doesn't save that much, needing a sqrt commitment anyway, and computing all the proofs is time consuming)?

dankrad avatar Jul 21 '20 22:07 dankrad