homomorphiclistdedup

Same hash by list content regardless of order of tree rotations and internal structure (UPDATE there is a way to create collisions but it doesnt happen by accident)

Collision resistance is backed by subsetSum (which is npcomplete) wrapped around a prime, or the secureHash used to generate arbitrary mySum of leafs (recommend SHA256), or the secureHash used to wrap a forkEditable list in a leaf (recommend SHA256), whichever is weaker. Recommend 192 bit integers if your system cant stand even 1 collision, but remember this is experimental.

hash(listX) = pair(mySum(listX)%globalModulus,myMult(listX)%globalModulus)

mySum(listX) = isSparseRange(listX) ? 0 : sum_y in listX_(mySum(y)*globalLeafMult^index(y,x))

myMult(listX) = isLeaf(listX) ? globalLeafMult : multiply_y in listX_(myMult(y))

TODO verify this math matches the code (which passes testcases).

public Node concat(Node u){
	if(!hashType.equals(u.hashType)) throw new RuntimeException("Different hashType");
	return new Node(
		primeWrappedSum.add(primeWrappedExponential.multiply(u.primeWrappedSum)).mod(hashType.globalModulus), //primeWrappedSum
		primeWrappedExponential.multiply(u.primeWrappedExponential).mod(hashType.globalModulus), //primeWrappedExponential
		hashType,
		size+u.size,
		this,
		u
	);
}


/** Used for sparse skipping */
public Node concatEmptyIndexs(long skip){
	if(size+skip >= 1L<<62) throw new RuntimeException("Too big size="+size+" skip="+skip);
	BigInteger mult = hashType.globalLeafSize.modPow(BigInteger.valueOf(skip), hashType.globalModulus);
	BigInteger newPrimeWrappedExponential = primeWrappedExponential.multiply(mult).mod(hashType.globalModulus);
	return new Node(primeWrappedSum, newPrimeWrappedExponential, hashType, size+skip, low, high); //FIXME high increased
}

Node xyxyxyx1 = x.concat(y).concat(x).concat(y).concat(x).concatEmptyIndexs(5000).concat(x).concat(y);
Node xyxyxyx2 = x.concat(y).concat(x).concat(y.concat(x).concatEmptyIndexs(2000).concatEmptyIndexs(3000).concat(x).concat(y));
System.out.println("xyxyxyx1=?xyxyxyx2 "+xyxyxyx1.equals(xyxyxyx2)+" (should be true)");
System.out.println("xyxyxyx1=?x "+xyxyxyx1.equals(x)+" (should be false)");

-------17---------
x=(uflist 9609110632821099184720144627494243658949682713196039209566106573938631700942 31551012845001747590937092469480532957557770726186508812414983709910907978975)
y=(uflist 76309505868621361192350376444870359513504574261348155147173694778426689072030 31551012845001747590937092469480532957557770726186508812414983709910907978975)
axyb=(uflist 46773681182835161823145831770327389805102893842101644342830061710999795361109 49188428448760845229681202359497175158962690161120219443948173811054007020171)
aaxybxb=(uflist 50979028163982315493858839390115625548125798570055502840739946663071919026238 52142849170775610954740420475276613123209539861504737643136909397707229752196)
ayxb=(uflist 74608399847825824232405158723323598015766279597891507563209241470516307852414 49188428448760845229681202359497175158962690161120219443948173811054007020171)
? aaxxbxb=(uflist 12113351593172715895487934525735717904234292777693250123511538218100374146455 52142849170775610954740420475276613123209539861504737643136909397707229752196)
? aaxybxb=(uflist 50979028163982315493858839390115625548125798570055502840739946663071919026238 52142849170775610954740420475276613123209539861504737643136909397707229752196)
true (should be true)
false (should be false)
false (should be false)
aaxybxb=(uflist 50979028163982315493858839390115625548125798570055502840739946663071919026238 52142849170775610954740420475276613123209539861504737643136909397707229752196)
axayxbb=(uflist 50979028163982315493858839390115625548125798570055502840739946663071919026238 52142849170775610954740420475276613123209539861504737643136909397707229752196)
xyxyxyx1=?xyxyxyx2 true (should be true)
xyxyxyx1=?x false (should be false)
-------18---------
x=(uflist 28417395258083018011263405218373568984698891952171568086378176218293599030082 103041204296607381900478922833472054308286857258011329863045095827643226652233)
y=(uflist 92114537568440393936478568559804135624999871995750474595418755852245596160069 103041204296607381900478922833472054308286857258011329863045095827643226652233)
axyb=(uflist 91084008511013865256402401754633329830420876336509983271590000033489470242160 103293608908583264930309609679424327848244014593640385589896650712361269731378)
aaxybxb=(uflist 69465736314381713323353679922867078980268937117464780866273587111851384802422 84319431598572213792083200216274752497619910496055452296483065761532238022031)
ayxb=(uflist 22239990045800347403867089361244567381355344494231307360283110477667627751452 103293608908583264930309609679424327848244014593640385589896650712361269731378)
? aaxxbxb=(uflist 48731943561564166185399280507363188617223879220097674622547208801540670576864 84319431598572213792083200216274752497619910496055452296483065761532238022031)
? aaxybxb=(uflist 69465736314381713323353679922867078980268937117464780866273587111851384802422 84319431598572213792083200216274752497619910496055452296483065761532238022031)
true (should be true)
false (should be false)
false (should be false)
aaxybxb=(uflist 69465736314381713323353679922867078980268937117464780866273587111851384802422 84319431598572213792083200216274752497619910496055452296483065761532238022031)
axayxbb=(uflist 69465736314381713323353679922867078980268937117464780866273587111851384802422 84319431598572213792083200216274752497619910496055452296483065761532238022031)
xyxyxyx1=?xyxyxyx2 true (should be true)
xyxyxyx1=?x false (should be false)
-------19---------