Full Transcript for Canonical Cache Representation

you again. Job Snijders 3:36 Hey George, good to be here. George Michaelson 3:37 So last time we were talking about a body of work you've been doing in RPKI that's a little less about measurement, although it was informed by measured observations you were making in the ecology, and it has a measurement story we might come back to. But I know that you have had a long-term interest in the idea we need to understand the shape of the RPKI information space, and I'm intrigued by how you can build and bootstrap something to tell us about the state of RPKI. What have you been doing here? Job Snijders 4:12 So a number of years ago, in 2020-ish, I set up a project called RPKI Views. You can access the website on rpkiews.org, and the idea of the project simply was: I want to capture all the RPKI data. If I capture all the RPKI data and make it accessible again in a structured fashion, like that, I can just send somebody a URL like, "Look, this was yesterday's RPKI data, that helps us reason and discuss events in the RPKI. George Michaelson 4:45 So we have history here. There's this amazing investment, a repository of knowledge of states of BGP maintained at the University of Oregon route views, and I'm looking route views, RPKI view. It resonates, right? Job Snijders 5:01 Yeah, yeah, yeah. I love route views. I've used it so many times throughout my career to understand what happens in a particular event, like who were the parties that were involved, what were the routers sending each other in terms of messaging, and I've used route views so many times to explain to my bosses, like well, you know, yesterday it's George Michaelson 5:22 really become a critical resource for analytics in BGP and for research publishing in BGP. We recently spoke with Thomas Holterbach and Thomas Alfwar from Strasburg, and they made a distinction in their service. They take feed from RIS, feed from Route Views, feed from BMP sources, but they've decided to offer service in a three-month view because they feel the cost of maintenance of a lifetime history is beyond the scope for your project. But in constructing RPKI views, you're hoping to manage the data retention problem, aren't you? You want to hold history. Job Snijders 6:01 Yes, I want to capture everything and store it forever. George Michaelson 6:05 Wow, that's that's a big ambition. Job Snijders 6:08 Yeah, yeah, yeah. So I really liked the sort of simple access of route views that they had an open directory structure, and it was categorized by year, by month, by day, and then for a particular hour, you could download the data that that happened in that hour, and I thought to myself, I want to access RPKI data in a similar way, and it didn't exist. Like it was not another project that had the granularity I was looking for. So I started by running the validation process, and then simply taking the cache directory that is the resulting state and wrapping that in a compressed tarball. So using [George: yeah] standard George Michaelson 6:49 Use the tools Job Snijders 6:49 yeah standard utilities gzip and George Michaelson 6:52 so the analytics here are take the date you want unpack the tarball perform operations on its contents compared to some other state job done [Job: right] standard Unix tools approach. Job Snijders 7:03 Yeah. Keep it simple. George Michaelson 7:05 So I like this because I love things that leverage the tools we all know and love, and I like simple solutions. But there is a cost here that's probably highly inefficient given the nature of the data we're dealing with, because a snapshot view of a repository, the global repository state in any point in time includes a large amount of data that didn't change from yesterday. So there's a component of cost here that feels inescapable. You're growing a huge problem. How big was your data set when you kicked this off? Job Snijders 7:36 Yeah, in the early days it was like 112 megabytes per snapshot, and already back then people pointed out to me like, man, that that is big, and why can't I download the difference? But in constructing the snapshots, constructing a differential was expensive on the server side. So, and it's also challenging to explain like how do you operate the differentials? [George: Yeah] So I was like, okay, yes, I agree. It costs a little bit more. George Michaelson 8:04 This is a problem for later in the design hypothesis you're expecting. Job Snijders 8:08 And back then, this space was cheap, right? George Michaelson 8:10 Yeah. So if we branch sideways, last time we spoke, you were telling us about the Erik protocol, named in memory of Erik Bais, and you kind of mentioned in passing that something you'd been exploring was idempotency in this data and ideas around canonical form and structurally canonical forms, and interests me that we're now in a different perspective considering archives and efficient packing and maintenance of data over a data set that you have already been thinking, what would this look like in its most canonical form? In a form I could understand and introspect over and intuit. Is this part of the process you were going through thinking about this? Job Snijders 8:54 I'm going to be very, very honest. The process was majorly inspired by the financial constraints I was running into. I needed it to be cheaper. [George: Yeah]. To give you a perspective, so in 2020, a snapshot would be 112 megabytes, and that meant I could take quite a few snapshots each and every day. And the storage requirements back then, I estimated them to be around 10 terabytes per year, and people would

sometimes donate a hard disk here and there, and we build large storage arrays using ZFS, and you know hosting a few terabytes of data. Yeah, it's an investment, but it was doable. But if we look at the cost of storage today and how the RPKI has grown to be roughly 5, 600 megabytes per snapshot with multiple nodes. Right now, the original approach of RPKI views is 50, 60, terabytes per year. George Michaelson 9:53 That's untenable growth for what is, forgive me if I'm wrong, essentially a self-funded project. Job Snijders 10:00 I could not run that as a hobby, and when I approach sponsors, I'm like, I need 100 terabytes per year extra. [George: yeah], a lot of sponsors are like, that's a lot, Job. [George: Yeah] that is a lot. So, and if I look at the size of the RPKI database, a validated cache is around one gigabyte, and the change rate per day is roughly 500 to 1000 megabytes. Like out of the 500,000 objects, about 180 change. So I thought to myself, a snapshot should not be larger than a gigabyte, and the change rate is less than a gigabyte. So there must be some way to more efficiently store the data as it is discovered. George Michaelson 10:46 Well, my highfalutin idea that concepts that float around in Erik about canonicalization and data structure didn't motivate you, but you're actually playing in the same space, aren't you? [Job: Yeah, yeah] You need to construct an interior state of the data and its change that is efficient and reproducible. Job Snijders 11:05 Right. So they do intersect, but the motivation was my wallet. George Michaelson 11:10 Yeah. So what is the intersection here? Job Snijders 11:14 To develop the ERIC protocol, I bumped into an obstacle where I recognized, in order to prove the correctness of the ERIC protocol, I need a way to efficiently express the state of a derived validated cache. So I came up with an idea called CCR, canonical cache representation, and the idea of CCR is that you sort of like what you have for BGP in MRT and what you have for DNS in DNStab, and for just raw Ethernet frames, you have pcap. And I thought to myself, we need a tool in the RPKI ecosystem to accurately and efficiently and performantly capture what were the inputs into the process and what was the output at a given point in time, George Michaelson 12:01 so this is a space that I think has been in IETF for a very, very long time, and we have things like CBOR and CDNS as approaches to constructing canonicalized states. Often on the wire, they may operate in higher levels, and so decisions are made in things like CDNS. We can reconstruct the query, but we've decided not to be able to reconstruct everything about the encapsulating packets that sent it. So various decisions get made. Did you have to make a conscious decision to discard something in CCR? Job

Snijders 12:37 No, no. I think I managed to make a lossless image of George Michaelson 12:41 wow. So, what encoding do you use for this canonical form? Job Snijders 12:46 You're gonna love this. My reasoning was we use DER distinguished encoding rules. George Michaelson 12:51 Oh, this for every last time. [Job: Yeah, yeah]. Oh, my least favorite protocol. So, you're using the binary efficient, archaic 1960s encoding. [Job: Absolutely] George Michaelson 13:04 Do you have a particular library for ASN one that you like to use? Job Snijders 13:09 I use libcrypto, which is the C sort of standard interface, and there's two implementations: Open SSL and Libre SSL, and that is usually what I work with. George Michaelson 13:20 Yeah, I spent some time using older libraries, and Christian Huitema from INRIA had access. He may well have authored a really lovely encoding library. I know that there are some highly efficient Java encoding models that people have used at places like BBN. Russ Housley, I think, maintains his own code that he uses to validate ASN.1 specs he sees in passing in the for Job Snijders 13:44 every language for every system there are ASN.1 libraries you can work with it in Python [George: yeah] the NLNet team did a great job George Michaelson 13:55 you're never going to make me change my mind I hate it but anyway you chose it it's your decision you're using ASN one. Job Snijders 14:01 Allow me to convince you. So we have CCR, and on the input side, it has a field called the manifest state, and this is basically a list of hashes of the manifest objects that contributed towards the validated ROA payload state. That is the output. George Michaelson 14:19 So it sounds very similar to aspects of the Merkle tree behavior that you discussed in Erik last time. We have now taken namespace- based objects and converted them to instances of hashes that are efficient statements of change over data. So I like this so far. You convinced me last time. We're now talking an initial block of hash state, Job Snijders 14:42 right? Not only it contains the hash, but also fields like the size of the object and the canonical location of the object, which is the subject information access field George Michaelson 14:54 (SIA field) from an x509 certificate relating to this object. Job Snijders 15:00 And it uses the SIA field verbatim. So this means that in the construction of a CCR, you maintain pointers to the memory regions of the objects that you're later going to serialize to disk. George Michaelson 15:13 Yeah, because these names, the SIA references, become useful performing behaviors like classic validation, path building inside the cryptographic hierarchy. These are aspects that can be useful for introspecting about the data. [Job: Right], they're kind of important index qualities in this information space. Job Snijders 15:32 So, in essence, the CCR contains fragments, literal fragments of the underlying manifest objects that are used to construct the input, and by using fragments, if you put this data together in, say, a tar file, you have repeating data because the fragment appeared in the manifest, of course. But now, if you put the manifest and the CCR together in a tar file, the fragment is repeated in the CCR, and then if you do compression, [George: yeah] like Zstd compression, you get insane efficiency rates because Zstd is like, well, I've seen this string of bytes. George Michaelson 16:12 You in effect have given it a catalog of the strings it's going to subsequently contain, and allowed it to maximize its Lempel ZIF like dictionary construction to say these instances are known. Here's the token that is 10 to 1 20, to 1 shorter than the data you're going to need. So you preload the compression dictionary by pre providing the string sets that are going to appear. [Job: Right. That's really smart. Job Snijders 16:41 Yeah. Well, it was more something I discovered as I went along because for the Erik protocol development, I needed a way to compare rsync RDP and and Erik, and then I came up with CCR, and then later on, I bumped into this problem that RPKI views storage requirements were becoming too costly to sustain, and I thought to myself, "What tools do I have to express the state of the cache?" And I realized, like, well, we did the CCR project to support the ERIC protocol development, but CCR is also a standalone tool that can be used to reconstruct points in time. And then I put the objects and the CCR's together in a tar file, and I ran the compressor, and I was just amazed by how small it had become. George Michaelson 17:31 So you had a size you mentioned for the size of this data. If you perform the fetching from all the repositories, you've said it's around 500,000 objects. [Job: Yeah, yeah, yeah], and the objects are somewhere between the 2k size. [Job: Yes], this is building up to about 500 meg of data. [Job: Yes] you now perform CCR. Job Snijders 17:53 It goes to like a gigabyte. George Michaelson 17:54 So a gigabyte, you perform CCR to canonicalize this and construct something that is a efficiently encoded state. What does the size become? Job Snijders 18:05 So a CCR object is around 20 megabytes, George Michaelson 18:09 a gig to 20 meg. Job Snijders 18:11 But it's it's only references to the objects in a gigabyte, right? George Michaelson 18:15 Ah, so it's a cataloging state, a reduction to 20 meg from the gig. Okay. Job Snijders 18:22 Yeah. And if you compress a CCR, if you compress one CCR object, it compresses to around 10 megabytes. Now, if you put multiple CCRs together in a tar file and compress

that tar file, guess what? It compresses to 10 megabytes. [George: Because] you have so much redundant data if you put the CCRs next to each other, and the change between one CCR to the next CCR, and because it's ASN one, there is a canonical form of how you express the bytes on the wire. This means there's a lot of duplicity in the data, and you end up storing only the differences between the CCRs and the RPKI. George Michaelson 19:06 Right. So if you were a conscious agent constructing the efficient storage model, you would in effect be recapitulating what Z standard does, constructing compression states over data with regular recurring sequences. And you're saying, why reinvent the wheel? You have to have the sequence of CCRs because you're snapshotting. The point is to detect when things change. The CCR simply encodes the hashes, and if there's no change in the hashes, the compression will elide them to the tokens. [Job: Yep] And then you're left with this token changed. That becomes the growth. It's functionally close to the constant size with a small amount of growth. It's basically saying this 10 meg 100 times if nothing changes. Job Snijders 19:52 Exactly, and that means I can have many many data gatherers around the world, which is what RPKI views has. There is. Nodes that are in Bangalore, in Sydney, in Amsterdam, in Zurich, and all of them produce CCRs as they produce validation states, and they send the CCRs to a central location. The central location puts all the CCRs together in a tar file. Zstd compresses the tar file. It sees that there's lots of duplicate data, and you end up with tar files where every day is represented by roughly a gigabyte worth of data. So now, instead of storing three terabytes per month, I am storing 30 gigabytes per month, and I have higher resolution. So with the previous RPKI views model, I could instrument say 5000 snapshots per month. With the new model, I can produce 40,000 snapshots per month. So this is a fantastic optimization in terms of higher precision, higher resolution. We have more data points, so we have a better insight in how exactly the RPKI state is changing as a distributed database, George Michaelson 21:07 and this similar to route views. This is not a single point collection. You've just said this is the representation of visible validation states in time across quite a large distributed surface. Job Snijders 21:19 Right, and and there is not only geographic distribution, but also distribution in terms of say synchronization transport. So some nodes are do RRDP, and if that doesn't work, they'll fall back to RSync. Some nodes do only RSync. Some nodes reset their RRDP state, so they follow only the the full snapshots. So some have IPv4 access. Some also have IPv6 access. George Michaelson 21:43 And you

are encoding this in your collection structure, so you understand these differences. Job Snijders 21:49 For all of them, I collect the CCRs, and then I can compare the outcomes, and I can look at like does one node arrive at very different states than other nodes? George Michaelson 21:59 Are you starting to see these variations in behavior? Job Snijders 22:02 yeah, there are variations. They're small, but it's it's not zero. And all these variations are in what I call an RPKI spool file. So an RPKI spool is this method of put a bunch of CCRs and the raw data together in a particular structure using a particular file naming scheme and offer that as a Zstd compressed form. Now, this is something I want to emphasize. RPKI views collects raw data. We do this because I believe that future researchers may have requirements that I cannot foresee. I don't know what tomorrow's researchers will want to inspect. So by capturing the the raw data, the DER encoded certificates and manifests and ROAs and CRLs, etc. etc. I do not put any limits on what future researchers can do with the data, and I think this is very very important to emphasize. George Michaelson 22:59 Well, this is similar to the Oregon Route Views repository. This is not their statement of claim of the important bits of BGP. It's just what BGP is, and other people come to that place and use that information to construct their view. This is the interesting part I want to introspect on. So, if you were a researcher or a student looking for a thesis topic and it emerges into some aspect of the RPKI ecology, what you're doing, Job, is you're providing a fundamental data source for these people to do their research IN - no constraints. Job Snijders 23:36 Yep, and it's now affordable because you, as you know, on my laptop, I have a few gigs of storage available, and I can easily fit like a month worth of RPKI data in 30 gigabytes. George Michaelson 23:48 So there is, of course, the data processing cost. You now have incurred a runtime cost to decompress the stream, to find the differences, to construct the states you want to experiment on in data terms, nothing is free, but in terms of the space component of cost, you've solved a problem. Do you notice a time burden processing spool files? Job Snijders 24:11 Yes, absolutely. And this is the engineering trade-off. In order to to replicate the data in a real-time fashion, that would be very costly. But if I segmentize the data into segments of a day, so 24 hours, and I follow the UTC time zone to organize it all, and then focus on yesterday's data, deduplicate all that data, order it, sort it, have mix it in with the CCRs, and then compress the result resulting tarball. What ... the system I constructed basically gives you yesterday's data with a few hours of delay. So

the nodes are collecting data throughout the day. They send it all to a centralized location, and at 6 a.m. of every day, I take yesterday's data and do the. Compactization process, and that takes about two hours, and then the result is published. So you get access to yesterday's data with roughly an eight-hour delay. George Michaelson 25:11 That's not bad. Job Snijders 25:12 It's not bad, but it's high latency replication, and that's okay because the gains are in the storage. George Michaelson 25:18 So if you were looking to introspect about growth properties of RPKI in the world. I feel from what you've said about this system, we can already answer primary questions: What is the rate of change? What is the rate of growth? What is the distribution of participation by discrete source node? These classes of questions you could actually track trivially as first-order measurements against the data set. If you want to say what happens if I change the ROA for 1.1 dot 1.1, or I'd like to see the beaconing that I know is happening now, you are diving into this information space, reading it to find instances of prefix and origin. That's costly. So there's a class of meta state about the health of RPKI that's available fairly simply, and there's a class of in system data it's available, but there's a compute cost against the compression. But that's a trade off, like you said. It's engineering, Job Snijders 26:15 and the RPKI spool idea. My idea is that some researchers may prefer to use parquet files. Some researchers may prefer to use Postgres or MySQL or CSV or something else, George Michaelson 26:30 or even ASN Job Snijders 26:32 or yeah, whatever. And you take the data from RPKI views, you convert it into something that is suitable for your research, and there's no limitation because you're given the raw data, so you transform it into whatever research infrastructure you're you're using, and off you go. George Michaelson 26:50 So have you written a suite of tools to read and construct these files that people can download? Job Snijders 26:56 There is a little bit of tooling available. It's called RPKI Spool-CLI. Fedor Vompe from Deutsche Telekom is maintaining that tool. There is an Internet draft that explains the RPKI Spool format for parties to have a stable reference. How is this data constructed? What are the naming conventions? What are the the exact data formats and encodings that are used because this is an open data set. So I felt it is really important to document how does this system work. How can I interact with the data? What can I expect from an RPKI spool file? George Michaelson 27:34 And now for your own research, because you also have been interested in the dynamics of the system. This has become the fundamental underpinning. This is the data source

you come to to look at what's going on. Job Snijders 27:45 Yeah, and I have I have found amazing things in the RPKI spool files. With the previous RPKI views, I had trouble working with the data I produced. It was so many gigabytes of data per day that that comparing [George: yeah] it was challenging. But now that the data is in much smaller form, so let me give you an example. I discovered that under certain circumstances, the APNIC hosted CA system can reintroduce a ROA from months ago, and I've been in touch with the APNIC staff, and we're we're debugging why this happens, but old files reappearing is a very quirky behavior, and it warrants investigation, and it's probably George Michaelson 28:29 and it's something you were able to see by looking at what was cropping up as the differencing between the states of this system. Job Snijders 28:35 Exactly, and another example, I discovered that there was a backdating software defects in the ARIN hosted CA system because sometimes ROAs would appear in yesterday's RPKI spool that were dated like months or long time ago. George Michaelson 28:54 Yes, there's this problem that the cryptographically assured statement I made this on Thursday doesn't strongly equate to file marked information in a file system. This is the date the bytes were written to disk, [Job: right] And in the protocol, we make strong cryptographically validated asserts. I know when I did this, but on disk, well, that's a bit more. Job Snijders 29:16 But it was just on disk. They were backdating the validity window. [George: Oh wow!] so what had happened was they have a feature in their web UI where you can change an existing ROA, [George: right] And instead of reissuing a new ROA, they took data from the old ROA and the validity window and the CMS signing time copied over from the older version of such object. George Michaelson 29:37 So it's strictly clear in this cryptographic model, it's not actually possible to change a signed object that occurred back then. It's a new object is made that contains parts of the bit stream that was signed over, but they were copying the bits of the bit stream that really shouldn't have been Job Snijders 29:57 exactly exactly. And with RPKI. Data. I had evidence like, hey, your system is not fully complying with the agreed upon IETF standards. So it's it's really cool how this platform of open data collection is helping the participants in the ecosystem to improve their practices and find software defects and then fix them because we now have great visibility into how the machinery is working. George Michaelson 30:25 Yeah, I really like this job. I like this quality that you can be involved in a system, designing it, arguing, defending, proposing, and separately just measuring. Here's a measurement. Here's a collection exercise. Here's everything that we have ever seen at the synchronization rate held in a way that I can keep doing this and scale this to meet future growth. I think that's really great, Job. Job Snijders 30:49 Yeah, and to give you another example, this data set it informs the standards development process. So some time ago, work was done on a particular field of signed objects called the CMS signing time, and in the CMS you have two ways of expressing the time. You can express the time in a certain format called generalized time, or you can express the time as a POSIX timestamp, so the seconds since january 1, 1970. So there's two ways to encode a timestamp, and while we were revising some aspects of the signed object templates, it dawned upon me that it is actually quite unhelpful to have two ways to do the same thing. George Michaelson 31:32 Yeah. Job Snijders 31:32 And what if somebody by accident [George: yeah] puts in both? George Michaelson 31:37 And what if they don't agree? And Job Snijders 31:38 both the timestamps. And what if they don't agree? So what I did was I took the RPKIviews data and I parsed all the objects for like a really long multi-year period, and then I could make an argument to the community and I said, "Hey, apparently nobody ever ever uses the binary form of the signing time, so it is safe to deprecate the use of the binary form. George Michaelson 32:05 This is a great example of the value of a deep time repository like RPKI views or route views. You can make a strong assertion: I checked back. Yeah, nobody's doing it. It's never been done. Job Snijders 32:18 And if we would not have had RPKI views. George Michaelson 32:21 It'd have been an open question, right? Oh, what if somebody is doing this? This is risky. No change. [Job: Yeah] Job Snijders 32:27 yeah. And the effect would have been we cannot change the standard because we lack that information to make an informed decision on. George Michaelson 32:34 Yeah, I think you're right. This kind of facility is what makes it possible to advance the technology we're depending on, Job, that's been absolutely fascinating. Job Snijders 32:45 And let me share one more fun fact. I took a look at ROA creation times, and then I mapped that to days after month, and I discovered something funny. People don't like changing ROAs on the weekends. In the RPKI views data, you can very clearly see that there is a different churn on business days versus Saturdays and Sundays. So, yeah, there's incredible insights to be derived from this data. Like, when do companies make changes? George Michaelson 33:17 We should inform the operators' union that they are not required to work BGP on weekends. Job Snijders 33:24 Yeah, exactly. And you know, this extends, of course, to understanding what are the change windows freezes around like when is it safe to perform. George Michaelson 33:31 It has aspects of that societal social component of how complex system works. Job Snijders 33:38 Human behavior is bleeding through into this data, and we can now try and analyze it. George Michaelson 33:44 Yeah, that's a good one. Job, Job Snijders 33:45 so call out to the community. [George: yes?] RPKI spools is a format you can use if you're a researcher. I'd be happy to help you if you have questions about the format. So please reach out to me if you have an RPKI related project and the project needs data because maybe I can help you set up your your analytics pipelines or maybe your use case can help inform how we better describe what the system looks like. So researchers take this as an open invite. RPKI data is available at a huge discount. It's available for free. It's only one gigabyte per day, so yeah, I hope to be collaborating with people and in that way do cool things with RPK views. George Michaelson 34:31 That's great. Thank you, Job. We'll talk to you again. Job Snijders 34:48 Thanks, George. George Michaelson 34:50 If you've got a story or research to share here on Ping, why not get in contact by email to ping at APNIC. net or via the APNIC social media channels. Also, remember the measurement at APNIC. net mailing list on orbit is there to discuss and share relevant collaborative opportunities, grants and funding opportunities, jobs and. Graduate placing, or to seek feedback from the community on your own measurement projects, be sure to check out the APNIC website for all your resource and community needs. Until next time.