Jamtis address checksum algorithm selection

[rbrunner7]

Monero addresses need an incorporated checksum so apps can check whether an address is valid or not. Monero 95-character addresses had that from day 1, inherited from CryptoNote, in the form of 4 bytes / 32 bits containing a hash over address data. You can e.g. see the checksum of a Monero address if you input it here or here.

@Tevador, the "inventor" of Jamtis, proposed to use a special kind of polynomial for the new Jamtis addresses to be used for Seraphis. See chapter 6.4 of their Jamtis "paper".

The choice between hash and polynomial was discussed during an MRL meeting on November 9, 2022, as can be seen in the meeting log. The result was the following advice of @UkoeHB to @DangerousFreedom1984:

I'd tentatively go for a checksum (we can revisit this as needed). You can use the seraphis hashing interface to access blake2b, which is faster than keccak.

Later, after the meeting which they did not attend, Tevador came into the MRL IRC channel to discuss this issue further. You can follow the discussion that took place here: https://libera.monerologs.net/monero-research-lab/20221109#c157273

IMHO that discussion added info that had not yet been brought up in the MRL meeting:

1. There are only 40 bits for the checksum, not 64 like we assumed during the meeting, thus room for less bits from a hash, and from that less safety.
2. To my surprise, calculating such a polynomial checksum does not need a lot code, but looks almost trivial, putting high complexity arguments into perspective.
3. Bitcoin already uses such checksums for its Bech32 addresses, as it seems with success and so far without anybody error-correcting those contrary to advice in the spec.

Thus at least in my understanding the decision what to use still hangs a bit in the air. I feel it would be good to have more security and consensus here, so we could go ahead with implementing Jamtis addresses and also risk making such addresses public - with a disclaimer of course, but with a good chance that they will stand.

In a private discussion with koe I got the impression that he would not veto the use of polynomials, and on the other hand it looks like Tevador could arrange with hashes although those being "a bit clunky" as they wrote on IRC.

[tevador]

Write-up/analysis/proposal here: https://gist.github.com/tevador/50160d160d24cfc6c52ae02eb3d17024?permalink_comment_id=4382275#gistcomment-4382275

[rbrunner7]

Thanks for that proposal, @tevador.

I have one question though where I don't know yet what to make of it, and where I would like to learn more and hear your opinion about it.

If I understand correctly a while after the bech32 scheme was defined, something called "a weakness" was detected. I quote from a text that you yourself and @DangerousFreedom1984 linked to:

BIP173 today uses M=1, but it is now known that this has a weakness: if the final character is a "p", any number of "q" characters can be inserted or erased right before it, without invalidating the checksum.

It seems this led to a quite elaborate search for a better value for M and definition of the improved bech32m scheme.

You write about a similar search in the case of Jamits addresses:

Bitcoin devs also developed a tool to search for optimal values of M, but our search space is 1000x times larger and it might be infeasible to do an exhaustive analysis like they did.

My question is basically this: Is it possible, in theory, that your proposal also has at least such a weakness? And if yes, what's a sensible reaction to such a risk?

Is this unlikely to such a dregree that we can just "live with that risk"? Was M = 1 a particularly bad idea, and we know now that if you take any another constant "with more bits sets" or whatever such weaknesses are a lot less likely?

By the way, I wonder whether hash algorithms were ever subjected to such a rigorous examination whether there really are no feasible "error patterns" that lead to the same hash, or the same x cropped bits of the hash. I could readily imagine that total security and total certainty are impossible to get, and that whatever you do it's always possible there is such a weakness.

[tevador]

Here is an analysis of the bech32 issue: https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb

Basically, the choice of the constant M determines only the strength of the checksum against insertion errors at the end of the string. It seems that choosing M to be a low order polynomial is a particularly bad choice. In any case, inserting (or deleting) characters from an address makes it invalid regardless of the validity of the checksum.

Testing one value of M requires about 35 billion polymod evaluations, which might be feasible to do. Overall, a high-order polynomial like the one I chose has a low chance of being affected by this issue.

[tevador]

Thanks to @gingeropolous for providing access to the Monero Research Computing network. I put the Threadripper machine to good use.

I managed to find much better cyclic codes for the checksum than what I proposed above. The new algorithm is following:

# Jamtis address checksum algorithm proposal

# cyclic code based on the generator U1PIRGA7
# can always detect 1-5 errors
GEN=[0xf0732dc147, 0xa8b6dfa68e, 0x193fabc83c, 0x322fd3b451, 0x640f37688b]

# cyclic code based on the generator 5155TAUI
# can always detect 1-4 errors
#GEN=[0x284a5eabd2, 0x5094a9d2ad, 0xa12947847a, 0xa021f08dd, 0x14042a9193]

M = 0xfffffffff7

def jamtis_polymod(data):
    c = 1
    for v in data:
        b = (c >> 35)
        c = ((c & 0x07ffffffff) << 5) ^ v
        for i in range(5):
            c ^= GEN[i] if ((b >> i) & 1) else 0
    return c

def jamtis_verify_checksum(data):
    return jamtis_polymod(data) == M

def jamtis_create_checksum(data):
    polymod = jamtis_polymod(data + [0,0,0,0,0,0,0,0]) ^ M
    return [(polymod >> 5 * (7 - i)) & 31 for i in range(8)]

# test/example

CHARSET = "xmrbase32cdfghijknopqtuwy1456789"

addr_test = (
    "xmr1majob1977bw3ympyh2yxd7hjymrw8crc9kinodkm8d3"
    "wdu8jdhf3fkdpmgxfkbywbb9mdwkhkya4jtfnod5h7s49bf"
    "yji1936w19tyf39o6ypjo9n64runqjrxwp6k2s3phxwm6wr"
    "b5cob6c1ntrg2mugeocwdgnnr7u7bgknya9arksrjore7wh")

addr_data = [CHARSET.find(x) for x in addr_test]
addr_enc = addr_data + jamtis_create_checksum(addr_data)
addr = "".join([CHARSET[x] for x in addr_enc])

print(addr)
print("len =", len(addr))
print("valid =", jamtis_verify_checksum(addr_enc))

I recommend to use the first generator U1PIRGA7, which has by far the best performance of all the codes I tested. However, it has a small flaw. Its false positive rate for certain (unlikely) arrangements of 6 errors is about 16x worse than a 40-bit hash-based checksum (comparable to a 36-bit hash). I don't think this is a problem in practice (it still outperforms the current 32-bit checksum used by Monero).

If there was opposition to the generator because of this flaw, there is an alternative generator 5155TAUI, which is not as good as the first one, but it has no drawbacks compared to a 40-bit hash.

I have documented the whole process how I found these generators in this gist, so anyone should be able to easily reproduce my results.

[tevador]

I've done some basic insertion error analysis of the two proposed generators (based on the bech32 sage code from here).

I found that the previously proposed constant M = 0xffeffffeff had one insertion error mode with a false positive rate of 2^-35, so I've updated the constant to M = 0xfffffffff7, which has no insertion errors above 2^-40.

[tevador]

I ran some extended tests and found that U1PIRGA7 can detect 5 errors up to 994 characters and 5155TAUI can detect 4 errors up to 545 characters. Both of these significantly exceed the current Jamtis address size at 196 characters, but the numbers can be relevant if we wanted to use the same checksum for other uses such as invoices or pre-signed transactions.

[tevador]

Pieter Wuille ran his own search based on our parameters and managed to find another "supergenerator" EVNOAKQC. If I add it to my results, it looks like this:

EVNOAKQC: max4=500 max5=500 max6=24 err5=0.000000 err6=1.140717 avg5=0.000000 avg6=0.904762 GEN=[0x77ef85534c, 0xe5cf9a07b8, 0x89ddb08a79, 0x5bb9f111fb, 0xb7237223df]
U1PIRGA7: max4=500 max5=500 max6=13 err5=0.000000 err6=15.346780 avg5=0.000000 avg6=1.545813 GEN=[0xf0732dc147, 0xa8b6dfa68e, 0x193fabc83c, 0x322fd3b451, 0x640f37688b]
AJ4RJKVB: max4=500 max5=500 max6=13 err5=0.000000 err6=15.346780 avg5=0.000000 avg6=1.564299 GEN=[0x54c9b9d3eb, 0xa3d1f786f6, 0xfa17f08e5, 0x15527a91ca, 0x20e4e1a394]
VRSOEBL7: max4=500 max5=123 max6=26 err5=0.282867 err6=1.025742 avg5=0.047074 avg6=0.817349 GEN=[0xfef9872ea7, 0xbfe39e586e, 0x3dd7b894dc, 0x71edf5a991, 0xe38b7b530b]
FKFN98KS: max4=500 max5=130 max6=26 err5=0.289107 err6=1.009149 avg5=0.042873 avg6=0.831064 GEN=[0x7d1f74a29c, 0xf07c794031, 0xa8aae6a44b, 0x1907cd4896, 0x320d1eb505]
DEE30B1D: max4=500 max5=129 max6=29 err5=0.296906 err6=0.995276 avg5=0.049757 avg6=0.764013 GEN=[0x6b9c302c2d, 0xd73860585a, 0xec62c0149d, 0x9ad7802913, 0x7dad90520f]
FVK7D3HH: max4=500 max5=121 max6=21 err5=0.292227 err6=1.012096 avg5=0.048907 avg6=0.859303 GEN=[0x7fe8768e31, 0xf5c2ed196b, 0xa9c5ceb2d6, 0x1b8919e0a5, 0x3710b7e54a]
JKHOGKBA: max4=500 max5=127 max6=22 err5=0.274547 err6=1.080168 avg5=0.042294 avg6=0.860180 GEN=[0x9d2388516a, 0x78579486d4, 0xf0adb908a1, 0xa90bf69142, 0x1a157d2284]
3EJU3UBP: max4=500 max5=138 max6=26 err5=0.297946 err6=1.015542 avg5=0.033664 avg6=0.841875 GEN=[0x1ba7e1f979, 0x371f5356db, 0x647c360cbf, 0xc2ea6c1957, 0xcd86ccb287]
KVDQ5Q0V: max4=500 max5=126 max6=32 err5=0.311466 err6=0.995733 avg5=0.056371 avg6=0.776661 GEN=[0xa7dba2e81f, 0xdf5d57417, 0x11fb3a4c07, 0x23a6f0bc0e, 0x471fe1781c]
0S7SR3A6: max4=500 max5=145 max6=21 err5=0.289107 err6=1.073390 avg5=0.035648 avg6=0.857036 GEN=[0x70fcd8d46, 0x45d1f9a8c, 0x2f8bbb038, 0x5a363e059, 0x15657649b]
5155TAUI: max4=500 max5=146 max6=23 err5=0.315105 err6=0.991495 avg5=0.038737 avg6=0.778061 GEN=[0x284a5eabd2, 0x5094a9d2ad, 0xa12947847a, 0xa021f08dd, 0x14042a9193]
RJ7I0PVJ: max4=500 max5=125 max6=29 err5=0.317185 err6=0.995053 avg5=0.054974 avg6=0.719604 GEN=[0xdccf2067f3, 0xfbdcd06eef, 0xbfb9a07cfe, 0x3d63d05dd5, 0x70d7301f83]
7RGCN5R5: max4=500 max5=140 max6=27 err5=0.308866 err6=1.023173 avg5=0.039775 avg6=0.822074 GEN=[0x3ee0cb9765, 0x77d383abea, 0xe5e59752f4, 0x89dbbe04e1, 0x5bb5f889c2]
QKDE8B2P: max4=500 max5=132 max6=23 err5=0.287547 err6=1.108732 avg5=0.045631 avg6=0.872560 GEN=[0xd51ae42c59, 0xe875c8589b, 0x98bb14951f, 0x7926b92a17, 0xf21f66d127]
O2IM6DP1: max4=500 max5=121 max6=32 err5=0.327585 err6=0.995260 avg5=0.063879 avg6=0.728596 GEN=[0xc0a5633721, 0xc91a566b62, 0xda34ac77e4, 0xfc3b4ccee8, 0xba661dbcf0]

EVNOAKQC seems to have no drawbacks, so it's the clear choice for our checksum.

[tevador]

Pieter and atomfried have both been running a search for the past few days and we have a total of 5 supergenerators now. The top candidate is 3BI5PLC1. I don't expect any major improvements since the 6-error rate is already close to 1.0.

3BI5PLC1: max4=500 max5=500 max6=29 err5=0.000000 err6=1.045999 avg5=0.000000 avg6=0.818232 GEN=[0x1ae45cd581, 0x359aad8f02, 0x61754f9b24, 0xc2ba1bb368, 0xcd2623e3f0]
EVNOAKQC: max4=500 max5=500 max6=24 err5=0.000000 err6=1.140717 avg5=0.000000 avg6=0.904762 GEN=[0x77ef85534c, 0xe5cf9a07b8, 0x89ddb08a79, 0x5bb9f111fb, 0xb7237223df]
6342T7JF: max4=500 max5=500 max6=18 err5=0.000000 err6=2.123248 avg5=0.000000 avg6=0.948887 GEN=[0x30c82e9e6f, 0x619049b9fe, 0xc32087f3d5, 0xce130f46a3, 0xde649aac66]
U1PIRGA7: max4=500 max5=500 max6=13 err5=0.000000 err6=15.346780 avg5=0.000000 avg6=1.545813 GEN=[0xf0732dc147, 0xa8b6dfa68e, 0x193fabc83c, 0x322fd3b451, 0x640f37688b]
AJ4RJKVB: max4=500 max5=500 max6=13 err5=0.000000 err6=15.346780 avg5=0.000000 avg6=1.564299 GEN=[0x54c9b9d3eb, 0xa3d1f786f6, 0xfa17f08e5, 0x15527a91ca, 0x20e4e1a394]

Finding one such generator takes on average about 250 core-days of CPU time.

[tevador]

I updated the specs with a checksum algorithm based on the generator 3BI5PLC1.

Here is an overview of the performance of various checksums when applied to a 196-character Jamtis address. The column "detection" refers to the number of errors that can always be detected. "Max5" and "Max6" are the maximum spans when 5 and 6 errors can always be detected, respectively. "Rate5" and "Rate6" are the worst-case false positive rates for lengths of up to 196 characters, multiplied by 2^40 (lower is better).

Checksum	size	used by	detection	Max5	Max6	Rate5 *2^40	Rate6 *2^40
code(3BI5PLC1)	40 bits	XMR (jamtis)	5	994	29	0.000000	1.045999
code(J3PBP3J1)	40 bits	BCH (cashaddr)	4	130	33	0.692608	1.001845
40-bit hash	40 bits	-	0	-	-	1.000000	1.000000
32-bit hash	32 bits	XMR (legacy)	0	-	-	256.000000	256.000000
code(TMKLTI)	30 bits	BTC (bech32)	3	18	8	1007.952788	1068.701701

[rbrunner7]

This algorithm selection looks done, up to the detail that 3BI5PLC1 is the "generator" to use, so I close this issue.