fjahr
commented
10 months ago I think you meant 2pm UTC and 3pm CET, which is also what the timestamp says.
Of course, fixed, timezones.... 💀
Closed fjahr closed 9 months ago
fjahr
commented
10 months ago I think you meant 2pm UTC and 3pm CET, which is also what the timestamp says.
Of course, fixed, timezones.... 💀
Sjors
commented
10 months ago Hash: 28039075f34ef65f9faff36a5141ce35a9b322600a263d4cf4cbb5d3e45390fe
In case you need it: final_result.txt.gz (4.9 MB)
0xB10C
commented
10 months ago It's a match! :tada:
The SHA-256 hash of the result file is: 28039075f34ef65f9faff36a5141ce35a9b322600a263d4cf4cbb5d3e45390fe
Total runtime: 6:03:28.581414
jurraca
commented
10 months ago Matched as well :triumph:
The SHA-256 hash of the result file is: 28039075f34ef65f9faff36a5141ce35a9b322600a263d4cf4cbb5d3e45390fe
Total runtime: 9:34:04.141037Not a match for me but very happy the fix for the previous bug now works and we are getting matches! This looks already much better than I expect a few weeks ago when I had the idea for this feature :)
My hash is b118079898b62383f13a81269367e45adc24a015e5f8a83799fc14517411c637 FWIW.
So, comparing the logs it looks to me like there is probably a slight different from the RPKI data. Comparing to @Sjors I found one duplicate less and 11 invalids more. That's probably where diff is coming from but I expect it to be small. I'm sharing my result here if someone wants do compare but I would also like to receive the result from one of you so I can look into it.
Additionally, I would be happy if someone can share their out/rpki/rpki_raw.json, there we can see what caused the actual validation differences. It's a pretty big file so it probably can't be shared here directly even after compression.
Sjors
commented
10 months ago @fjahr WeTransfer: https://we.tl/t-iqJn05yzgb (34 MB)
0xB10C
commented
10 months ago I've noticed that the final_results.txt file contains AS37963, but also aS30844, and As51528, and as200890. Is the final_results.txt file relevant for next steps in the asmap process? Does it make sense to standardize this to uppercase (e.g., always "AS1234")?
jurraca
commented
10 months ago Here's my final_result.zip @fjahr . (q: how are you uploading zip files to this repo directly?) (edited upload)
0xB10C
commented
10 months ago (q: how are you uploading zip files to this repo directly?)
You can just drag-and-drop it into the comment field here or use the paper clip icon on the top right.
fjahr
commented
10 months ago I've noticed that the final_results.txt file contains
AS37963, but alsoaS30844, andAs51528, andas200890. Is the final_results.txt file relevant for next steps in the asmap process? Does it make sense to standardize this to uppercase (e.g., always "AS1234")?
Oh, very interesting. I didn't notice that yet, whenever I write it explicitly in kartograf I do 'AS' but I will look into it. In the back of my mind I always had the idea that writing AS explicitly was redundant anyway, so when should just drop it and save those bytes. I will test if that even breaks Sipa's compression code and if not, I will simply do that instead :)
Sjors
commented
10 months ago Keeping the AS prefix makes it marginally more human readable and easier to copy-paste into google. These extra bytes don't make into the final bitcoin binary I assume, so it's probably fine to just keep them.
0xB10C
commented
10 months ago Looking through the file, I found it interesting that there are duplicate assignments for IP-net to ASN: e.g., 126 entries for 2001:503:eea3::30/128 with different ASNs. Not sure if that's to be expected. I probably need to look into the whole asmap process a bit more.
FWIW here's the diff -patch final_result_0xb10c.txt final_result_fjahr.txt between fjahr's and my file. No difference between sjors and my file - I guess that's to be expected when we get the same hash.
45.132.[188-191].0/24 which I'm missing147.28.8.0/23 AS58367 and 147.28.8.0/24 AS58367 147.28.9.0/24 AS58367 are the same result, just differently written. A .. 8.0/23 net is the same as a .. 8.0/24 + a .. 9.0/24 net. Not sure how to solve this? Maybe always trying to build the biggest supernet for an ASN? This might also reduce the file size a bit?*** final_result_0xb10c.txt 2023-12-21 22:15:19 +0100
--- final_result_fjahr.txt 2023-12-21 21:03:35 +0100
***************
*** 113800,113806 ****
--- 113800,113827 ----
45.132.185.0/24 AS35830
45.132.186.0/24 AS35830
45.132.187.0/24 AS35830
+ 45.132.188.0/24 AS3970
+ 45.132.188.0/24 AS47065
+ 45.132.188.0/24 AS61574
+ 45.132.188.0/24 AS61575
+ 45.132.188.0/24 AS61576
+ 45.132.188.0/22 AS3130
45.132.188.0/22 AS3970
+ 45.132.189.0/24 AS3970
+ 45.132.189.0/24 AS47065
+ 45.132.189.0/24 AS61574
+ 45.132.189.0/24 AS61575
+ 45.132.189.0/24 AS61576
+ 45.132.190.0/24 AS3970
+ 45.132.190.0/24 AS47065
+ 45.132.190.0/24 AS61574
+ 45.132.190.0/24 AS61575
+ 45.132.190.0/24 AS61576
+ 45.132.191.0/24 AS3970
+ 45.132.191.0/24 AS47065
+ 45.132.191.0/24 AS61574
+ 45.132.191.0/24 AS61575
+ 45.132.191.0/24 AS61576
45.132.192.0/24 AS210636
45.132.193.0/24 AS39351
45.132.194.0/24 AS61272
***************
*** 560369,560375 ****
147.28.6.0/24 AS61575
147.28.6.0/24 AS61576
147.28.7.0/24 AS3130
! 147.28.8.0/23 AS58367
147.28.10.0/24 AS47065
147.28.10.0/24 AS61574
147.28.10.0/24 AS61575
--- 560390,560397 ----
147.28.6.0/24 AS61575
147.28.6.0/24 AS61576
147.28.7.0/24 AS3130
! 147.28.8.0/24 AS58367
! 147.28.9.0/24 AS58367
147.28.10.0/24 AS47065
147.28.10.0/24 AS61574
147.28.10.0/24 AS61575
You could also have a two-round process. First round like we did above, where some people share more details to figure out the differences. Then in a second round, which skips the download step, everyone applies a patch to reconcile or get rid of the conflicting entries. And then re-run the steps.
fjahr
commented
10 months ago Keeping the AS prefix makes it marginally more human readable and easier to copy-paste into google. These extra bytes don't make into the final bitcoin binary I assume, so it's probably fine to just keep them.
I am keeping the AS in but explicitly format it to be all-caps now every time I write it.
Maybe always trying to build the biggest supernet for an ASN? This might also reduce the file size a bit?
I am currently not in favor of this since it would make debugging/analyzing the result harder and in terms of the file size I think in the compressed state this doesn't have much impact, if it's not resolved completely. It would potentially also mess with the coverage statistics of the network, depending on how it's implemented.
I found it interesting that there are duplicate assignments for IP-net to ASN
These shouldn't have been there. I found they are coming from IRR and from my understanding, this isn't normal usage. I checked some entries and it seems more like these are there to not block some experiments. Either way, I have resolved this in the same way I am doing it in PRKI, where duplicates are very common.
Example:
route: 45.132.188.0/24
descr: RPKI Experiment
origin: AS61575
notify: rw@rg.net
mnt-by: MAINT-RGNET
created: 2020-11-28T19:56:21Z
last-modified: 2020-11-28T19:56:21Z
source: RIPEI also found another issue where a handful of IPv6 prefixes had leading zeros, i.e. 2401:0001::/32. These only disappeared later in the process when the IP is converted to an int and so this influenced results.
All the issues are resolved in master and I will do some more testing before we can to another test. Thanks a lot everyone again for joining and testing!
fjahr
commented
10 months ago You could also have a two-round process. First round like we did above, where some people share more details to figure out the differences. Then in a second round, which skips the download step, everyone applies a patch to reconcile or get rid of the conflicting entries. And then re-run the steps.
I think this is a bit too complicated for starting out. I think the regular process should be very quick by default so that we can be sure it isn't blocked. It seems pretty promising that we can do a collaborative launch with a group and if the majority has the same result, it's good to merge. If we don't get a majority we simply try again.
Figuring out the differences may be easy sometimes but often I think this could create a lot of research work and/or the result may not be satisfactory for everyone. We would need some kind of definition for what is ok and not ok and then come to a rough consensus agreement on which way to go for each line of the diff. I am a bit afraid we may not have everyone's attention all of the time and so if a diff analysis gets drawn out do we still have enough of the original runners engaged when it's resolved? Or would it be ok if someone else comes in who was not part of the original group but then reviews the diff and says that it is alright? I see a lot of unanswered questions so I would like us to learn a bit more along the way before we commit to figuring out the diffs every time. Of course, it's always encouraged to look at the diffs and figure out where they came from and what they mean, if there is something to be concerned or a sign for improvement. I just would like to bank the whole process on that part right now.
It also makes the process a bit more vulnerable to attacks, I think. If we try to reconcile all differences the process can be blocked by a single person submitting a bogus result that is impossible to resolve because it's not based on real data. With the "federated" approach above there would at least be a significant part of the group that submits such results and may be more obvious what is happening if 3-5 never seen before github nyms join the process rather than just one.
fjahr
commented
10 months ago Hi and happy new year! 🎆
I have tagged release 0.4.0 which has the fixes I mentioned previously and a few other nice usability improvements, like an added progress bar during RPKI validation, showing a countdown during the wait, printing the current Kartograf version etc.
I want to do (yet another) test run with this version. The previous run already was a success IMO since it showed that except for me everyone else agreed on the result and the differences between me and the rest were in the "explainable" category. But doing another run would be great because we can't test too much and the fixes I have introduced should lead to an easier time drilling down more into the diff.
I propose tomorrow 2:00 pm GMT (1704463200) and I hope it's not too short notice. Thanks again! 🙏 🙏 🙏
./run map -w=1704463200 -irr -rv@brunoerg did you end up having a result hash for the previous run BTW?
brunoerg
commented
10 months ago @fjahr no, I had a problem on my laptop, fortunately I just bought a better one and will have the runs faster 🚀
fjahr
commented
10 months ago @fjahr no, I had a problem on my laptop, fortunately I just bought a better one and will have the runs faster 🚀
Ok, thanks for the heads-up!
fjahr
commented
10 months ago I propose tomorrow 2:00 pm GMT (
1704463200) and I hope it's not too short notice. Thanks again! 🙏 🙏 🙏./run map -w=1704463200 -irr -rv
Feel free to use 0.4.1 for this one instead, where I have improved the formatting of the countdown, something I forgot to include in the release previously: https://github.com/fjahr/kartograf/releases/tag/0.4.1
0xB10C
commented
10 months ago I propose tomorrow 2:00 pm GMT (
1704463200) and I hope it's not too short notice. Thanks again! 🙏 🙏 🙏
Reminder, this is in 1h and 30 min. I'll be joining.
brunoerg
commented
10 months ago I'll be joining!
The countdown is great, nice job!
fjahr
commented
9 months ago My result hash is4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b
0xB10C
commented
9 months ago I've got a match on 4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b!
edit: Here's an asmap map generated from final_resuls.txt (IPv4 only). Color is based on the AS.
jurraca
commented
9 months ago I got 3d42c9c376ebcbe2e21ddf1ba9951e7940dbbf7e6e1f7df9bc182b57d760d768.
0xB10C
commented
9 months ago @jurraca can you upload your final_results.txt here?
Mine is here final_result.txt.gz
Emzy
commented
9 months ago I've got a match on: 4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b Total runtime: 14:56:59.428796 (slow i3 thin client)
Sjors
commented
9 months ago I also got 4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b.
Total runtime: 2:38:01.512775 which is 30 minutes faster than last time.
jurraca
commented
9 months ago @jurraca can you upload your
final_results.txthere?
here it is final_result.txt.gz
0xB10C
commented
9 months ago @jurraca can you upload your
final_results.txthere?here it is final_result.txt.gz
Alright. Yeah, that's a bigger diff. Don't have the time to step through it in detail.
I've noticed that there are overlapping mappings to the same AS in my final_results.txt file. For example:
2.189.0.0/16 AS49666
2.189.1.0/24 AS49666The /16 should already cover the /24 mapping.
fjahr
commented
9 months ago I've noticed that there are overlapping mappings to the same AS in my
final_results.txtfile. For example:2.189.0.0/16 AS49666 2.189.1.0/24 AS49666The /16 should already cover the /24 mapping.
Yeah, this is an interesting observation. We can look into doing this as a final step but we need to think about an algorithm to do this efficiently. One edge case that we would need to handle as well is if the file had an additional entry that is from a different AS and is between the two entries in terms of specificity, then we would not be able to do this, i.e. we would also need to check that no entry like 2.189.0.0/20 AS1337 exists. We can probably do this reasonably easily after the file result file is sorted. I will check how often we see candidates to decide if this is worth the effort. Another small downside is that this new final result file becomes a bit harder to debug.
fjahr
commented
9 months ago Alright, nice, so we had 4/5 for the 4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b hash. @brunoerg did you get a result?
@jurraca was the dissenting hash and as @0xB10C said it's a pretty big diff this time. I could see in the logs that there are certainly differences coming out of RPKI again. So this is kind of the situation that I described above: we have a majority for one result and I would personally be fine with recommending the 4/5 hash to run it in their node based on this. It would still be a great idea to develop tools to check what input files caused the diff explicitly and what we can learn from that but actually figuring out which of these 1000+ differing lines would be preferred will take unreasonably long with the manpower available to us.
I am still very happy with these results :) These are two runs in a row were we just had one dissenting result which makes me more confident that this process is a viable solution. It was also not the same person that dissented so it doesn't seem to be a systemic issue afaict.
I will spend some time documenting the findings now. I will also open a PR here to demo what it would look like to make a compressed result part of the repo. Please let me know if you have any further feedback on the tools, process etc.!
fjahr
commented
9 months ago Here is the demo PR for the finalized asmap.dat file: https://github.com/fjahr/asmap-data/pull/6
Would be great to get some feedback from 1-2 of you whether you receive the same result and the process makes sense like this. Thanks you!
0xB10C
commented
9 months ago I've noticed that there are overlapping mappings to the same AS in my
final_results.txtfile. For example:2.189.0.0/16 AS49666 2.189.1.0/24 AS49666The /16 should already cover the /24 mapping.
Yeah, this is an interesting observation. We can look into doing this as a final step but we need to think about an algorithm to do this efficiently. One edge case that we would need to handle as well is if the file had an additional entry that is from a different AS and is between the two entries in terms of specificity, then we would not be able to do this, i.e. we would also need to check that no entry like
2.189.0.0/20 AS1337exists. We can probably do this reasonably easily after the file result file is sorted. I will check how often we see candidates to decide if this is worth the effort. Another small downside is that this new final result file becomes a bit harder to debug.
I took a quick look. Radix trees are commonly used as data structures in network routing for use-cases where you have entries with different network prefixes. There's a python package py-radix implementing a radix tree for python network addresses.
When building a radix tree from the addresses in final_results.txt, I check each prefix if there is already a prefix covering it. This seems to work well. However, I noticed there are a lot of cases where the smaller subnets have a different ASN than the subnet covering it.
import radix
with open("final_result.txt", 'r') as f:
rtree = radix.Radix()
for line in f.readlines():
ip_str, asn = line.strip().split(" ")
# check if there is already a prefix covering the current ip in the RadixTree
for rnode in rtree.search_covering(ip_str):
if asn != rnode.data:
print(f"{rnode.prefix} already covers {ip_str}, but {ip_str} has a different ASN of {asn} compared to {rnode.data}")
if len(rtree.search_covering(ip_str)) == 0:
rnode = rtree.add(ip_str)
rnode.data = asnThis prints 293720 lines similar to the following. The final_results.txt contains 1256210 entries. So about 23% are overlapping in some way.
1.0.128.0/19 (AS9737) already covers 1.0.129.0/24 (AS23969), but 1.0.129.0/24 has a different ASN!
1.0.128.0/18 (AS9737) already covers 1.0.129.0/24 (AS23969), but 1.0.129.0/24 has a different ASN!
1.0.128.0/17 (AS9737) already covers 1.0.129.0/24 (AS23969), but 1.0.129.0/24 has a different ASN!
1.6.224.0/22 (AS9583) already covers 1.6.226.0/24 (AS132215), but 1.6.226.0/24 has a different ASN!
1.6.224.0/22 (AS9583) already covers 1.6.227.0/24 (AS132215), but 1.6.227.0/24 has a different ASN!
1.6.228.0/22 (AS9583) already covers 1.6.229.0/24 (AS4755), but 1.6.229.0/24 has a different ASN!
1.7.140.0/22 (AS9583) already covers 1.7.142.0/24 (AS132215), but 1.7.142.0/24 has a different ASN!
1.7.148.0/22 (AS9583) already covers 1.7.151.0/24 (AS132215), but 1.7.151.0/24 has a different ASN!
1.7.160.0/22 (AS9583) already covers 1.7.161.0/24 (AS132215), but 1.7.161.0/24 has a different ASN!
1.7.160.0/22 (AS9583) already covers 1.7.162.0/24 (AS132215), but 1.7.162.0/24 has a different ASN!
...I don't know (as I'm still not familiar enough with asmap) if we want to prefer the larger prefixes or the smaller ones.
Emzy
commented
9 months ago When building a radix tree from the addresses in
final_results.txt, I check each prefix if there is already a prefix covering it. This seems to work well. However, I noticed there are a lot of cases where the smaller subnets have a different ASN than the subnet covering it.
AFAIK the more specific (smaller) subnet is always used for routing.
0xB10C
commented
9 months ago After taking a look at #6 and playing around with the asmap-tool, it seems that the tool takes care of it. After encoding and decoding the file, only the smaller (fewer IPs) prefixes seems to remain. E.g.:
... (from above)
1.7.160.0/22 (AS9583) already covers 1.7.161.0/24 (AS132215), but 1.7.161.0/24 has a different ASN!
1.7.160.0/22 (AS9583) already covers 1.7.162.0/24 (AS132215), but 1.7.162.0/24 has a different ASN!# in asmap.txt (decoded asmap.dat)
1.7.161.0/24 AS132215
1.7.162.0/24 AS132215I don't think you'd need to implement any deduplication or de-overlapping here then.
brunoerg
commented
9 months ago Alright, nice, so we had 4/5 for the 4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b hash. @brunoerg did you get a result?
Same hash: 4aba172195b8dc375c2bb1b39c3508f48c212cedc02983a7dc794a373820653b
fjahr
commented
9 months ago Thanks everyone for participating! This has been a great success! The collaborative launch feature has worked far better than I expected and we found and fixed several issues along the way.
I am closing this now but would like to do another one tomorrow in about 24 hours: https://github.com/fjahr/asmap-data/issues/7 I would be very happy if as many of you as possible could join again. My goal with this one is to have a 'clean' demo that makes it easier to grasp what the process will look like in the future when not as many issues arise as within this one. Upon success, I want use it as an example to show what we have achieved here :)
@brunoerg @Sjors @0xB10C @Emzy @jurraca
In Kartograf 0.3.1 a new feature was added that allows users to start the mapping process at the exact same time at a previously agreed timestamp. This has shown some promise to result in the same or at least very similar results for the final mapping file across several participants. If multiple participants get the same result independently, trust in the ASMap file is further minimized as the input data generation is effectively federated. From the point of the creation of the input data, the process of arriving at the final ASMap file is reproducible with open-source tools and thus completely trustless.
As a demo of how this could work in the future, I propose the following timestamp to start a mapping process collaboratively:
1702994400. This is Tuesday, December 19, 2023 2:00:00 PM GMT, the same time of day at which the Bitcoin Core IRC meeting happens on Thursdays.What you need to do to participate:
./run maponce before setting the collaborative launch. If you have used Kartograf in the past you will probably still need to upgrade to the latest version, 0.3.1 at least../run map -w=1702994400 -irr -rv. The program runs and waits until the timestamp is hit, you just need to ensure that your computer is running until then and let it finish the process.A few notes, especially if you have tried Kartograf previously:
Let me know if there are any questions. If you plan to participate, happy to see you confirm beforehand here as well.