,
6 tweets,
2 min read
Read on Twitter
And now for a discussion of exactly the sort of thing people come to Twitter for: How to do low latency multiplication in hardware. This is very different from the usual meaning of 'fast' multiplication, which is about reducing the total number of gates \1
Low latency is about reducing the depth of the circuit. Quadratic blow-ups are generally no big deal if all you care about is the depth and sizes are not truly massive. Using schoolbook multiplication when we multiply two n-digit numbers together it turns into n additions of \2
n-digit numbers. The carries are the real problem here. We can simplify things with one weird trick: To add together three numbers we calculate the 'carry' and 'non-carry' parts of the output. The non-carry is the xors, and the carry is \3
a 2-of-3 threshold shifted over one bit. Now we've taken adding three things and reduced it to two. We can apply this recursively and in parallel to make a circuit of logarithmic depth which gets the number of additions down to two \4
So the question is: Now that we have a single value which is the sum of two things, how to we get it down to a single value with a logarithmic depth circuit? The surprising answer is that as long as our upcoming operations are all simple arithmetic, we often don't have to! \5
For the case of an RSA-based VDF we can simply leave it as the sum of two things until the very final output must be calculated. This is another weird trick and it's hard to pin down a good intuitive reason for it but it does seem to be the best approach \fin
