...by Daniel Szego
"On a long enough timeline we will all become Satoshi Nakamoto.."
Daniel Szego

Monday, July 23, 2018

Optimizing IOU debts and mining

As we have seen in the previous blog, debt optimization is practically proposing a new directed graph structure in a way that balances of the individual accounts do not change. The easiest way to represent the debt graph is the adjacency matrix, where each A[i,j] element represents the the IOU contract from i to j. Based on that representation, we can formally define the balances of an account as well: 

Balance i = Sum (A[i,j]) - Sum k (A[k,i])

Considering a general mining process, there can be several {IT1, IT2, ... ITN} transactions issuing new IOU-s each transaction is signed by its creator. On top, there is a set of {OT1, OT2, ... OTN} optimization transactions either signed by trusted optimizer nodes, or by nobody. Both sets of transactions are in one two separate transactions pools. The idea of mining is to find a subsets of {IT1, IT2, ... ITK} and {OT1, OT2, ... OTK} transactions in a way that for all account balances, the change is initiated by only by the issuing transactions, meaning that:

Balance i (new) = Balance i (old) + Sum (OT[i,j]) - Sum k (OT[k,i]), where OT is a matrix built up by the {OT1, OT2, ... OTK} transactions. Certainly, the complexity of the network has to be reduced due to the optimization transactions, it is an open question how it can be measured. 

Based on these definitions, there can be a one shot or a two round transaction process: 
- if we imagine two rounds, the first round is a purely optimization round as the second one is a classical transaction round. 
- In a one shot process, both optimization and the new transactions take place.