Rust x Ethereum Day 2023 at The Foundry SF

Remco Bloemen presents on "Ruint"

Let's start with some existential questions.

Ruint is a Rust bigint library for large fixed-size unsigned integers.

Fixed size here means that the size is known at compile time,

unlike some other bigint libraries like GMP and numbigint, which I dynamically allocated and are therefore slightly less performant for the sizes we're using in Ethereum, which is mostly a uint256.

Rust has a bunch of built-in unsigned integers, just like u32, u64, all the way up to u128.

But unfortunately, the next 1 is missing.

LLVM, the compiler backend, supports arbitrarily sized integers quite efficiently.

But Rust doesn't expose it, so we need to do it ourselves.

I found that in some of the other existing libraries that are out there, the thing that annoyed me is that the function I needed wasn't implemented, and I need to somehow work around it, or some features weren't implemented.

Hard to do, so I wanted a library that was just turnkey, does everything you want.

In particular, I made sure that it's a drop-in replacement for something like U64.

All the standard library functions that you expect are there and do what you think they should be doing.

It is also, unlike some other libraries, actively maintained.

And a big shout out to James and Georgios for this, because I got distracted trying to onboard the entire world onto blockchain somehow.

Another question, why did I end up writing it?

So 1 of the main reasons is Rust's orphan rule.

If you build a library that exposes some important type and this type doesn't have some trait on it, like let's say 30, it is incredibly annoying to as a consumer of this library add this on.

You either fork the library or you need to use a new type on some other weird construction.

So that was the main motivation to build a library that has all the traits.

We just got const generics, and I so wanted a library where I could do uint and an angle bracket and tell it how many bits I wanted.

And I wanted to see if I could build something like that.

And I had some from a previous project, some really fast ports of GMP algorithms lying around that really needed a new home where people could actually use them.

So that's the motivation for starting this project.

They all have feature flags so you don't blow up your compile times if you don't need it.

The way dependency resolutions works is that whatever is needed in your entire project automatically gets enabled.

It's probably barely readable, but there's a whole list of traits it implements.

Lesson learned along the way is that these traits, like let's say SIRD or ARCFF, they upgrade sometimes.

And that is technically a break in chains, which would be really annoying because it multiplies over all these dependencies that are there.

So we're working on a solution there to support versioning of implemented traits, and probably all these feature tags will also have a major version associated with them, so that you could implement, let's say, 32 and enable 33, and even have both enabled concurrently, if that is what your project needs.

So now, I said it was mostly compatible with STD, and indeed, if you find anything non-obvious and different about these Uints versus the built-in native ones, that's a bug and you should report it.

The standard operators, plus, minus, multiply, et cetera, they wrap by default.

Kind of a design choice, the built-in Rust ones will panic in debug mode and then silently do undefined behavior in release mode, which is not a good idea.

The other thing is that shifts in Rust are a little bit awkward because if you give it A shift amount that is larger than the type itself, it's also undefined behavior.

And then some technical constraints, like some functions couldn't be made constant because of technical reasons.

Anyway, I recommend you read this part of the doc before you really go deep into it.

Now, I would be disappointing some members in the audience if I didn't present a little bit of moon math.

What this library actually implements is what in number theory is called a ring, which is the integers modulo 2 to the power something.

This has addition, like a ring has addition, subtraction, multiplication, et cetera, as you've learned it in primary school, but it also has an inverse, which is the anti-multiplication element.

It's basically a number that when multiplied, like, given a number, you can compare its inverse, and if you multiply the 2 together, you get the number 1.

Which is kind of like division, except we don't have fractions here.

in UN64 in this case, I can compute its ring inverse, and then the result will be this really bizarre looking 64-bit number.

But if you multiply that with a wrapping multiply with the original number, the result is indeed

And in fact, if you multiply by this number we just computed, it is kind of like dividing by the number

So I compute a number b here that is 57 times something.

And if I take that result and multiply it by A, I get my original number back.

So, yes, we've just divided by 57 doing a multiply.

Caveat, this trick only works if the number is — if this division is exact.

If it is not exact, you get some really weird odd number.

Another caveat is that these inverses only exist if the number you're inverting is comb prime with your modulus, meaning in this case that it needs to be an odd number.

So this only works for odd numbers and only when a division is exact.

But it's a really cool trick, and you can actually use it to optimize certain algorithms quite effectively, mostly because this inverse is actually also really easy to compute.

Another highlight, kind of along the lines of James' work as well, is how do we abuse the proc macros to make things easier on the developers?

1 of the things, and this is partially a motivation for writing this library as well, 1 of the things I realized is that Rust's tokenizer actually supports arbitrarily sized integers.

Like the token stream representation just has a string for the integer that is in your source code.

So the uint macro takes whatever Rust source you give it.

It finds all the integer constants and checks if it has a suffix that starts with a capital letter U.

The standard library types have a lowercase u.

If you do an uppercase U, it will get picked up by this macro.

It will parse it exactly the same way as Rust would do by itself, except it will do it in an arbitrarily sized type.

And it will do this, it will then produce a constant and substitute it in the output code.

So this basically allows you to just wrap a bunch of code in this UN macro and now you can write code using the ruined integers as if it's native Rust.

Another fun thing in the project is It has a little bot that I've been playing around with that automatically creates GitHub issues for any to-do comments that are in the code.

I'm a firm believer that you need to keep your project management as close to the source code as you can possibly do.

And this 1 allows you to just do your to-do management in the code system itself.

Other fun bits of code, like I mentioned, there's a couple of pretty sophisticated algorithms in there that I ported over from GMP.

There's Knud Division, which is an efficient division algorithm, and LemurGCT, which is a greatest common divisor algorithm that is also used for modular inverses.

This 1 is particularly fun because modular inverses are quite important in cryptographic applications.

And I'm fairly sure that this 1 is more performant than anything that's out there right now, even in the crypto-dedicated libraries.

So it will be fun to see that get a little bit more use.

Another fun bit of code if you're exploring the library is look at the Postgres integration.

I went quite overboard there and I tried to implement every single column type that could remotely be interpreted as an integer.

And in particular, the 1 that's kind of obvious, actually, the numeric type, which is the arbitrarily sized integers that Postgres supports.

But it turns out that the format is completely undocumented.

And I had to dig through the Postgres source code to figure out how that binary format actually works.

That code hasn't been updated since 94, I think, and it uses binary coded decimal.

So that was a good, fun bit of history there.

On the left, you see the function to compute the root, like square root, cubic roots, and higher order roots.

It uses a fun trick to speed up the process, where basically, it takes a double precision float approximation of the big end, uses float operations to create a first approximation of the result and then just does a couple of quick iterations to turn it into an exact value.

This is a way of designing fast algorithms.

And it's enabled by having another interesting piece of code that does a very precise conversion from a F64 double precision float to an unsigned integer.

Right now, it's, I think, entirely plain Rust, so very portable, but it doesn't have specific optimizations you can do in x86-64, which has some fun opcodes like mullx and addx and addc.

Similarly, ARC64, ARM, Wasm, all of them could benefit from more targeted optimizations.

Interesting thing that came up recently is like, hey, maybe we should have a RISC-V back end or a MIPS back end here, because it seems that people are now suddenly interested in compiling this thing to RISC-0 and Canon and Other completely new architectures.

If you want to implement traits, please do.

It's just an extra feature flag, and it will save people a lot of trouble because of the orphan rule.

A particular 1 that is still open and a nice beginner's task is numTrades, which has a lot of fun little trades like is 0 and is 1 and you name it.

Another thing is maybe extend it with more types.

Like I said, it has fast modular inversions.

Maybe we want to have a whole modular type where you have a compile time modulus, and then you can just instantiate this ring and do algebra in it, or prime fields even.

Like I said, this 1 is compile-time fixed size.

Maybe we do want a version that can leverage the same algorithms that have already been implemented, but use a runtime-sized type.

So where this 1 is kind of an array of digits, that 1 will be a factor of digits.

And right now, if you peer under the hood, you will see that it is uint bits, limps, which is a restriction of what Rust generic can currently do.

So, you need to provide the number of bits you want, but also how many 64-bit limbs that requires.

It will panic if you give the wrong number, like impossible numbers here.

And it would be nice to make it automatically compile time, compute how many limbs it needs.

But unfortunately, this is blocked on Rust upstream issues that have been open for a couple of years now.

So that will not be resolved anytime soon.

The other things, though, contributions more than welcome.

It's a fun little low stack, high impact project.

Hey, Have you considered adding support for SIMD?

That would fall under architecture-specific optimizations.

And for clarity, SIMD for parallel instructions was the question.

It also uses git blame to assign the GitHub issue.

I think we use it in some some places in some of the crypto math but the main usage will be when we move to an OP stack on something like OP Red and that whole thing will be built on top of all the foundations you've seen so far.

Hi, I was just wondering, well first, your blog and approximation theory changed my life.

But I was just wondering what is the most interesting or esoteric algorithm you had to implement for adding functionality to Ruin?


Speaker 0: Good. So welcome to the bottom of the stack. Let's start with some existential questions. What is it? Ruint is a Rust bigint library for large fixed-size unsigned integers.

Fixed size here means that the size is known at compile time,

Speaker 1: unlike some other bigint libraries like GMP and numbigint, which I dynamically allocated and are therefore slightly less performant for the sizes we're using in Ethereum, which is mostly a uint256. Rust has a bunch of built-in unsigned integers, just like u32, u64, all the way up to u128. But unfortunately, the next 1 is missing. This is a Rust choice, actually. LLVM, the compiler backend, supports arbitrarily sized integers quite efficiently.

But Rust doesn't expose it, so we need to do it ourselves. And that is what Ruin does. Heavy emphasis on developer experience. I found that in some of the other existing libraries that are out there, the thing that annoyed me is that the function I needed wasn't implemented, and I need to somehow work around it, or some features weren't implemented. Hard to do, so I wanted a library that was just turnkey, does everything you want.

In particular, I made sure that it's a drop-in replacement for something like U64. All the standard library functions that you expect are there and do what you think they should be doing. It is also, unlike some other libraries, actively maintained. And a big shout out to James and Georgios for this, because I got distracted trying to onboard the entire world onto blockchain somehow. Another question, why did I end up writing it?

So 1 of the main reasons is Rust's orphan rule. If you build a library that exposes some important type and this type doesn't have some trait on it, like let's say 30, it is incredibly annoying to as a consumer of this library add this on. It's impossible. You either fork the library or you need to use a new type on some other weird construction. You don't want this.

So that was the main motivation to build a library that has all the traits. Second is const generics. We just got const generics, and I so wanted a library where I could do uint and an angle bracket and tell it how many bits I wanted. And I wanted to see if I could build something like that. Turns out, yes, kind of.

And I had some from a previous project, some really fast ports of GMP algorithms lying around that really needed a new home where people could actually use them. So that's the motivation for starting this project. Starting with all the traits. I made them all optional. They all have feature flags so you don't blow up your compile times if you don't need it.

The way dependency resolutions works is that whatever is needed in your entire project automatically gets enabled. So that's cool. It's probably barely readable, but there's a whole list of traits it implements. Lesson learned along the way is that these traits, like let's say SIRD or ARCFF, they upgrade sometimes. And that is technically a break in chains, which would be really annoying because it multiplies over all these dependencies that are there.

So we're working on a solution there to support versioning of implemented traits, and probably all these feature tags will also have a major version associated with them, so that you could implement, let's say, 32 and enable 33, and even have both enabled concurrently, if that is what your project needs. So now, I said it was mostly compatible with STD, and indeed, if you find anything non-obvious and different about these Uints versus the built-in native ones, that's a bug and you should report it. But there are a couple of changes. The standard operators, plus, minus, multiply, et cetera, they wrap by default. Kind of a design choice, the built-in Rust ones will panic in debug mode and then silently do undefined behavior in release mode, which is not a good idea.

The other thing is that shifts in Rust are a little bit awkward because if you give it A shift amount that is larger than the type itself, it's also undefined behavior. We don't want that. And then some technical constraints, like some functions couldn't be made constant because of technical reasons. Anyway, I recommend you read this part of the doc before you really go deep into it. Now, I would be disappointing some members in the audience if I didn't present a little bit of moon math.

So this is the moon math section. What this library actually implements is what in number theory is called a ring, which is the integers modulo 2 to the power something. This has addition, like a ring has addition, subtraction, multiplication, et cetera, as you've learned it in primary school, but it also has an inverse, which is the anti-multiplication element. It's basically a number that when multiplied, like, given a number, you can compare its inverse, and if you multiply the 2 together, you get the number 1. Which is kind of like division, except we don't have fractions here.

So what does this number look like? I have an example on the right here. Like, if we take the number

Speaker 0: 57

Speaker 1: in UN64 in this case, I can compute its ring inverse, and then the result will be this really bizarre looking 64-bit number. But if you multiply that with a wrapping multiply with the original number, the result is indeed

Speaker 0: 1.

Speaker 1: And in fact, if you multiply by this number we just computed, it is kind of like dividing by the number

Speaker 0: 57.

Speaker 1: So I compute a number b here that is 57 times something. And if I take that result and multiply it by A, I get my original number back. So, yes, we've just divided by 57 doing a multiply. Caveat, this trick only works if the number is — if this division is exact. If it is not exact, you get some really weird odd number.

Another caveat is that these inverses only exist if the number you're inverting is comb prime with your modulus, meaning in this case that it needs to be an odd number. So this only works for odd numbers and only when a division is exact. But it's a really cool trick, and you can actually use it to optimize certain algorithms quite effectively, mostly because this inverse is actually also really easy to compute. So that's the moon math section. Another highlight, kind of along the lines of James' work as well, is how do we abuse the proc macros to make things easier on the developers?

1 of the things, and this is partially a motivation for writing this library as well, 1 of the things I realized is that Rust's tokenizer actually supports arbitrarily sized integers. Like the token stream representation just has a string for the integer that is in your source code. So the uint macro takes whatever Rust source you give it. It finds all the integer constants and checks if it has a suffix that starts with a capital letter U. The standard library types have a lowercase u.

If you do an uppercase U, it will get picked up by this macro. It takes whatever is in front of it. It will parse it exactly the same way as Rust would do by itself, except it will do it in an arbitrarily sized type. And it will do this, it will then produce a constant and substitute it in the output code. So this basically allows you to just wrap a bunch of code in this UN macro and now you can write code using the ruined integers as if it's native Rust.

Another fun thing in the project is It has a little bot that I've been playing around with that automatically creates GitHub issues for any to-do comments that are in the code. I'm a firm believer that you need to keep your project management as close to the source code as you can possibly do. And this 1 allows you to just do your to-do management in the code system itself. Fun little hack. Other fun bits of code, like I mentioned, there's a couple of pretty sophisticated algorithms in there that I ported over from GMP.

There's Knud Division, which is an efficient division algorithm, and LemurGCT, which is a greatest common divisor algorithm that is also used for modular inverses. This 1 is particularly fun because modular inverses are quite important in cryptographic applications. And I'm fairly sure that this 1 is more performant than anything that's out there right now, even in the crypto-dedicated libraries. So it will be fun to see that get a little bit more use. Another fun bit of code if you're exploring the library is look at the Postgres integration.

I went quite overboard there and I tried to implement every single column type that could remotely be interpreted as an integer. And in particular, the 1 that's kind of obvious, actually, the numeric type, which is the arbitrarily sized integers that Postgres supports. That seemed to make sense to implement. But it turns out that the format is completely undocumented. And I had to dig through the Postgres source code to figure out how that binary format actually works.

That code hasn't been updated since 94, I think, and it uses binary coded decimal. So that was a good, fun bit of history there. On the left, you see the function to compute the root, like square root, cubic roots, and higher order roots. It uses a fun trick to speed up the process, where basically, it takes a double precision float approximation of the big end, uses float operations to create a first approximation of the result and then just does a couple of quick iterations to turn it into an exact value. This is a way of designing fast algorithms.

And it's enabled by having another interesting piece of code that does a very precise conversion from a F64 double precision float to an unsigned integer. So some concrete questions. What are the next steps here? Obvious ones are more optimizations. Right now, it's, I think, entirely plain Rust, so very portable, but it doesn't have specific optimizations you can do in x86-64, which has some fun opcodes like mullx and addx and addc.

Similarly, ARC64, ARM, Wasm, all of them could benefit from more targeted optimizations. Interesting thing that came up recently is like, hey, maybe we should have a RISC-V back end or a MIPS back end here, because it seems that people are now suddenly interested in compiling this thing to RISC-0 and Canon and Other completely new architectures. More traits, always welcome. If you want to implement traits, please do. Just submit a PR, probably get included.

It's kind of 0 cost. It's just an extra feature flag, and it will save people a lot of trouble because of the orphan rule. A particular 1 that is still open and a nice beginner's task is numTrades, which has a lot of fun little trades like is 0 and is 1 and you name it. Another thing is maybe extend it with more types. Right now it's just unsigned integers.

Maybe we want signed integers too. Could be interesting. Like I said, it has fast modular inversions. Maybe we want to have a whole modular type where you have a compile time modulus, and then you can just instantiate this ring and do algebra in it, or prime fields even. A runtime-sized version.

Like I said, this 1 is compile-time fixed size. Maybe we do want a version that can leverage the same algorithms that have already been implemented, but use a runtime-sized type. So where this 1 is kind of an array of digits, that 1 will be a factor of digits. And right now, if you peer under the hood, you will see that it is uint bits, limps, which is a restriction of what Rust generic can currently do. So, you need to provide the number of bits you want, but also how many 64-bit limbs that requires.

It will panic if you give the wrong number, like impossible numbers here. And it would be nice to make it automatically compile time, compute how many limbs it needs. But unfortunately, this is blocked on Rust upstream issues that have been open for a couple of years now. So that will not be resolved anytime soon. The other things, though, contributions more than welcome.

It's a fun little low stack, high impact project. Should be fairly accessible. So yeah, hope to Your PR is there. Any questions? Hey, Have you considered adding support for SIMD?

That would fall under architecture-specific optimizations.

Speaker 2: And for clarity, SIMD for parallel instructions was the question. I have a quick 1. Just shout out for the GitHub action. That's awesome. Thanks.

Speaker 1: Yeah, you should check it out. It also uses git blame to assign the GitHub issue. If...

Speaker 2: I already said that. You love that action, man. Next. How does WordCoin use the Ruin library? Sorry?

How is WordCoin currently using this?

Speaker 1: I think we use it in some some places in some of the crypto math but the main usage will be when we move to an OP stack on something like OP Red and that whole thing will be built on top of all the foundations you've seen so far.

Speaker 2: Thank you.

Speaker 3: Hi, I was just wondering, well first, your blog and approximation theory changed my life. But I was just wondering what is the most interesting or esoteric algorithm you had to implement for adding functionality to Ruin?

Speaker 1: Oh, for sure the Lemur GCD. That 1 is a wild 1.

Speaker 3: Thank you.

Speaker 2: A Round of applause for Remco.

See all Paradigm transcripts on Youtube

Rust x Ethereum Day - Ruint