We looked at the formula for probability of cross shard transactions in both Omniledger and RapidChain.
The probability of cross shard transaction means, given any transaction from the blockchain, what is the chance of this transaction involving multiple shards, i.e the input UTXOs and output UTXOs are located in multiple shards. If they are all in one shard, then this transaction is not a cross shard transaction.
In OmniLedger:
Appendix C, formula 3, there is a small error.
Here n is the sum of all input and output UTXOs,
k is number of shards that need to participate in cross shard validation,
m is total number of shards,
P(n,k,m) is the probability of a transaction being in k shards.
In line 3, (m-k) / m should read (m-(k-1)) / m. Suppose the transaction has a total (n-1) UTXOs which are located in (k-1) shards. If we add 1 extra UTXO to make a total of n UTXOs and the transaction’s UTXOs are located in k shards, the probability should be (m-(k-1))/m. After this minor fix, the formula is correct.
In RapidChain:
In section 6.7, formula 10, we found the formula to be incorrect.
Here, u is total number of input and output UTXOs,
v is the number of shards where input UTXOs are located,
k is the total number of shards,
And 1-F(u,v,k) is the probability that the tx is cross-shard.
(1) The case u=v never happens, so that F(u,v,k) = 0, when u=v.
If we define number of input UTXOs as x and number of output UTXOs as y.
u = x+y
v <= x (one UTXO only belongs to one shard, otherwise, we need to sync UTXO for each transaction)
thus we always have u>v, because each transaction will have at least one output (y >=1).
(2) in v=1 case, all the input transaction is in one shard, so the probability of output transaction also in the same shard should be (1/k)^y. It doesn’t equal to (1/k)^u.
(3) in u=1 and v=1 case, it means the total number of transaction is one and the total number of input is 1, so there is no output transaction, which also does not make sense.
k: number of shards
u: #(input utxos) + #(output utxos) in tx
v: #(committees that stores at least one input utxo)
f(u,v,k): probability of tx is in one shard