Introduction
Introduction
Many blockchain networks, including bitcoin, use a Proof of Work procedure to find the hash of a block of transactions and rewards the node that finds this hash with a certain amount of cryptocurrency. This process, known as mining, wastes a lot of computational power -as well as energy- because the hashes it finds serve no purpose. Here we introduce the Proof of Useful Ruliad Work procedure, that is based on the Cuckoo Hashing Algorithm, that produces a hash of a block of transactions by finding a cycle of a determined size (this parameter determines the difficulty)between two hashing tables. The procedure is explained in the notebook.
Creation of two hash tables
Creation of two hash tables
We first create the two hash tables of size , where n is the number of bits in the hash function.
n
2
In[]:=
n=8
Out[]=
8
In[]:=
list1=List/@Range[1,]
n
2
Out[]=
{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13},{14},{15},{16},{17},{18},{19},{20},{21},{22},{23},{24},{25},{26},{27},{28},{29},{30},{31},{32},{33},{34},{35},{36},{37},{38},{39},{40},{41},{42},{43},{44},{45},{46},{47},{48},{49},{50},{51},{52},{53},{54},{55},{56},{57},{58},{59},{60},{61},{62},{63},{64},{65},{66},{67},{68},{69},{70},{71},{72},{73},{74},{75},{76},{77},{78},{79},{80},{81},{82},{83},{84},{85},{86},{87},{88},{89},{90},{91},{92},{93},{94},{95},{96},{97},{98},{99},{100},{101},{102},{103},{104},{105},{106},{107},{108},{109},{110},{111},{112},{113},{114},{115},{116},{117},{118},{119},{120},{121},{122},{123},{124},{125},{126},{127},{128},{129},{130},{131},{132},{133},{134},{135},{136},{137},{138},{139},{140},{141},{142},{143},{144},{145},{146},{147},{148},{149},{150},{151},{152},{153},{154},{155},{156},{157},{158},{159},{160},{161},{162},{163},{164},{165},{166},{167},{168},{169},{170},{171},{172},{173},{174},{175},{176},{177},{178},{179},{180},{181},{182},{183},{184},{185},{186},{187},{188},{189},{190},{191},{192},{193},{194},{195},{196},{197},{198},{199},{200},{201},{202},{203},{204},{205},{206},{207},{208},{209},{210},{211},{212},{213},{214},{215},{216},{217},{218},{219},{220},{221},{222},{223},{224},{225},{226},{227},{228},{229},{230},{231},{232},{233},{234},{235},{236},{237},{238},{239},{240},{241},{242},{243},{244},{245},{246},{247},{248},{249},{250},{251},{252},{253},{254},{255},{256}}
In[]:=
list2=List/@Range[1,]
n
2
Out[]=
{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13},{14},{15},{16},{17},{18},{19},{20},{21},{22},{23},{24},{25},{26},{27},{28},{29},{30},{31},{32},{33},{34},{35},{36},{37},{38},{39},{40},{41},{42},{43},{44},{45},{46},{47},{48},{49},{50},{51},{52},{53},{54},{55},{56},{57},{58},{59},{60},{61},{62},{63},{64},{65},{66},{67},{68},{69},{70},{71},{72},{73},{74},{75},{76},{77},{78},{79},{80},{81},{82},{83},{84},{85},{86},{87},{88},{89},{90},{91},{92},{93},{94},{95},{96},{97},{98},{99},{100},{101},{102},{103},{104},{105},{106},{107},{108},{109},{110},{111},{112},{113},{114},{115},{116},{117},{118},{119},{120},{121},{122},{123},{124},{125},{126},{127},{128},{129},{130},{131},{132},{133},{134},{135},{136},{137},{138},{139},{140},{141},{142},{143},{144},{145},{146},{147},{148},{149},{150},{151},{152},{153},{154},{155},{156},{157},{158},{159},{160},{161},{162},{163},{164},{165},{166},{167},{168},{169},{170},{171},{172},{173},{174},{175},{176},{177},{178},{179},{180},{181},{182},{183},{184},{185},{186},{187},{188},{189},{190},{191},{192},{193},{194},{195},{196},{197},{198},{199},{200},{201},{202},{203},{204},{205},{206},{207},{208},{209},{210},{211},{212},{213},{214},{215},{216},{217},{218},{219},{220},{221},{222},{223},{224},{225},{226},{227},{228},{229},{230},{231},{232},{233},{234},{235},{236},{237},{238},{239},{240},{241},{242},{243},{244},{245},{246},{247},{248},{249},{250},{251},{252},{253},{254},{255},{256}}
Hashing functions
Hashing functions
We then create two hash functions, each one assigns the position of the value to be stored in each of the two tables
In[]:=
hash1[x_]:=Hash[x,{"BLAKE2b",n}]+1
In[]:=
hash2[x_]:=Hash[x,{"BLAKE2s",n}]+1
Assigning the position of each entered value in each table
Assigning the position of each entered value in each table
We create a function that assigns each entered value into its corresponding table. By default, each element is assigned a hash value, and that value corresponds to its position in the first hash table. If that position is already taken by a previous value, then that value is taken to the position assigned by the second hash function to the second hash table. The same criteria is applied to the second hash table.
In[]:=
fill[x_]:=If[TrueQ[Length[list1[[hash1[x]]]]==1],AppendTo[list1[[hash1[x]]],x],If[TrueQ[Length[list2[[hash2[x]]]]==1],AppendTo[list2[[hash2[x]]],{hash1[x],x}],AppendTo[list1[[hash1[x]]],{hash2[x],x}]]]
Now we create the numbers to be entered into the tables. This can be changed to transactions in a blockchain network. Note that we aim to create a dense network by comparing the number of entries to the universe of numbers from where these entries are taken.
In[]:=
numbers1=RandomSample[Range[0,100000],]
2×n
2
Out[]=
We now apply the function we created to the list of numbers we just generated.
In[]:=
pairs1=fill/@numbers1
Out[]=
In[]:=
list1//Dataset
Out[]=
In[]:=
list2//Dataset
Out[]=
Data preparation
Data preparation
Now we just prepare the data for the bipartite graph we will generate
In[]:=
list1a=list1[[Flatten[Position[Table[Length[list1[[i]]],{i,1,}],_?(#>1&)]]]]
n
2
Out[]=
In[]:=
list1b=list1a[[Flatten[Position[Table[Length[list1a[[i]]],{i,1,Length[list1a]}],_?(#>2&)]]]]
Out[]=
In[]:=
Riffle[list1b[[All,1]],"l"]
Out[]=
{1,l,2,l,3,l,4,l,5,l,6,l,7,l,8,l,9,l,10,l,11,l,12,l,13,l,14,l,15,l,16,l,17,l,18,l,19,l,20,l,21,l,22,l,23,l,24,l,25,l,26,l,27,l,28,l,29,l,30,l,31,l,32,l,33,l,34,l,35,l,36,l,37,l,38,l,39,l,40,l,41,l,42,l,43,l,44,l,45,l,46,l,47,l,48,l,49,l,50,l,51,l,52,l,53,l,54,l,55,l,56,l,57,l,58,l,59,l,60,l,61,l,62,l,63,l,64,l,65,l,66,l,67,l,68,l,69,l,70,l,71,l,72,l,73,l,74,l,75,l,76,l,77,l,78,l,79,l,80,l,81,l,82,l,83,l,84,l,85,l,86,l,87,l,88,l,89,l,90,l,91,l,92,l,93,l,94,l,95,l,96,l,97,l,98,l,99,l,100,l,101,l,102,l,103,l,104,l,105,l,106,l,107,l,108,l,109,l,110,l,111,l,112,l,113,l,114,l,115,l,116,l,117,l,118,l,119,l,120,l,121,l,122,l,123,l,124,l,125,l,126,l,127,l,128,l,129,l,130,l,131,l,132,l,133,l,134,l,135,l,136,l,137,l,138,l,139,l,140,l,141,l,142,l,143,l,144,l,145,l,146,l,147,l,148,l,149,l,150,l,151,l,152,l,153,l,154,l,155,l,156,l,157,l,158,l,159,l,160,l,161,l,162,l,163,l,164,l,165,l,166,l,167,l,168,l,169,l,170,l,171,l,172,l,173,l,174,l,175,l,176,l,177,l,178,l,179,l,180,l,181,l,182,l,183,l,184,l,185,l,186,l,187,l,188,l,189,l,190,l,191,l,192,l,193,l,194,l,195,l,196,l,197,l,198,l,199,l,200,l,201,l,202,l,203,l,204,l,205,l,206,l,207,l,208,l,209,l,210,l,211,l,212,l,213,l,214,l,215,l,216,l,217,l,218,l,219,l,220,l,221,l,222,l,223,l,224,l,225,l,226,l,227,l,228,l,229,l,230,l,231,l,232,l,233,l,234,l,235,l,236,l,237,l,238,l,239,l,240,l,241,l,242,l,243,l,244,l,245,l,246,l,247,l,248,l,249,l,250,l,251,l,252,l,253,l,254,l,255,l,256}
Graph representation
Graph representation
We finally represent the bipartite graph and find the cycles, and the cycle size. The difficulty of finding a cycle of minimal size increases as the size of the cycle increases. These graphs might be of value as objects from the Ruliad.
Acknowledgements
Acknowledgements
This work is based on John Tromp’s Cuckoo Proof of Work algorithm. It benefited from discussions with Stephen Wolfram, Jonathan Gorard, James