Leader queue verification

[ineiti]

Once we have the verification functions in place, the leader should do the following:

• sort the transactions according to some random, deterministic sort algorithm (adding the current block's hash or so)
• check if the validation function works and flag Valid of the transaction accordingly

Then each follower node should go through the list and make sure that he gets the same results as the leader, else he should refuse to sign.

[pablo-lo]

For the first point, I have two (related) solutions, inspired by the ByzCoin paper section 3.6.1. In ByzCoin, they need a way to tie break between blocks, which is deterministic but has high entropy, something similar to what we need to sort the transactions. They do the following:

"One way to break a tie without helping selfish miners, is to increase the entropy of the output of the determinis- tic prioritization function. We implement this idea using the following algorithm. When a miner detects a key- block fork, it places all competing blocks’ header hashes into a sorted array, from low to high hash values. The array itself is then hashed, and the final bit(s) of this hash determine which keyblock wins the fork."

We will do something similar: Idea I

• First, we take the hashes of all the transactions and sort them.
• Then, we hash that sorted array again. This will give us a value which is deterministic for a given set of transactions, but can not be guessed by an attacker who does no know all the transactions in advance. We will refer to this value as the "salt".
• Now, we prepend the salt to each transaction's protobuf representation (or something alike) and hash this concatenation again. The outputs of this second hash are then sorted and this sorting defines the sorting of the transactions.

So essentially what we do is

• generate a deterministic but hard to guess salt from the transactions
• prepend this salt to a byte representation of the transaction and hash it
• sort the resulting hashes to determine how to sort the transactions.

In idea I, we have to do two sorting operations. The first on is only used to generate the salt. This could be avoided by XORing the byte representations of all the transaction and use the resulting bytestring as a nonce. Since XOR is commutative and associative, we can avoid sorting. we refer to this as idea II

@ineiti: Are there any security issues with this, what do you think? Also, do you have a preference on which approach to take? Personally, I prefer idea II, since I find it a bit heavy to sort everything twice, but could it be that idea I is more secure?