Pseudorandomly choosing the next leader at delegated proof of stake

Cryptographic secure random number generation is one of the biggest challenge for every blockchain protocol. It can be extremely important at different Nakamoto consensus or similar algorithms, because the next leader should be chosen with a cryptographically secure pseudorandom generator, otherwise denial of service attack can be easily carried out against the leader. At a delegated proof of stake system, however such an algorithm can be realized easily, and supposing that at least one node acts in an honest way producing real pseudorandom number, the result should be pseudorandom as well. The following algorithm sketch produces the required result:

- The actual leader node creates a private public key pairs and initiates a request for the delegate nodes producing a random number. This request also contains the public key that is actually related to the request. 

- The delegate nodes individually create a pseudorandom random number with some internal or hardware algorithm. These random numbers are encrypted by the public key of the request and spent back to the leader in an encrypted form. During this phase, the random information is encrypted, so practically, nobody can see or manipulate the exact random number. 

- The leader decrypts the with the help of the private key the random numbers and combines them into a final random number, like with the help of a similar algorithms: 

R1 XOR R2 XOR ... XOR Rn

or

sha256(... sha256(sha256(R1) XOR R2) ... XOR Rn)

at the end both the final random number and the private key is revealed in the blockchain, so everybody can proof if the choice algorithm was correct. 

If the random numbers are generated independently from each other and there is at least truly random number the result will be probably truly random as well. If the randomness of the numbers generated by the individual nodes can be checked, there can be a critpoeconomical incentive mechanism as well to reward or slash certain behaviors. 

There is one denial of service attack against the scheme though. If the leader does not reveal the information at the end of the round, like the random key or the random number at the end, a new leader should be chosen, however without the given pseudo-random number. This case requires further investigation. 

Blueprint of a deletable blockchain platform

Based on our previous blog, creating off-chain proofs, there might be the possibility to create a blockchain algorithm where you can actually delete. For the architecture we defined the following architectural considerations:

- The nodes taking part in the consensus should have an identity, a private and public key key pair where the private key is kept secret.

- The consensus must be implicitly or explicitly based on a quorum, meaning that two thirds of the nodes should sign a given piece of information with validity.

- The consensus can be an indirect quorum, like in Tendermin, where there are several rounds for the consensus, like one for choosing a leader node and proposing a block and a second one for validating the given node by a quorum. 

- On-chain governance must contain a transaction that adds new nodes of the system. After successfully adding a node to the system, the public key of a node (e.g. identity of a node) must be added to the blockchain.

- The blockchain in a classical sense contains only governance information, e.g. the public keys of the different validator nodes.

- There must be a mechanism and a special transaction for deleting validator nodes from the blockchain, like with the help of an explicit transaction, or with the help of an automatic mechanism, like if a validator does not sign a block for an amount of time, it will be deleted from the active validators. 

- The architecture prefers consistency against availability at network separation, so it can not be forked and can not be long range attacked, unless more than one third of the nodes private key is leaked. 

- Efficient network separation is a working denial of service against the architecture. 

- Non-governance information, like smart contracts, or cryptocurrency transactions must be built up in a account-state based fashion, meaning that for a getting a valid state of the system, it is enough to read the last valid state. 

- Non-governance information is not stored in blockchain but in a separate block that is stored off-chain and validated by an off-chain proof by the blockchain, see the following picture

:

- Validator nodes have a two level key mechanism: master key is the main key of the node, but in each round, the node creates a new private - public key pair where the public key is published into the blockchain. This round key is used to sign off chain blocks. 

- At each round validity of the off-chain information and data is validated by all of the validator nodes and signed by the public keys that are specific for a certain round. 

- An external observer can check if a given block is valid, by checking the public keys of the validator nodes and checking  if they really signed the given block. As public keys are individual for each round, both the exact round and the fact if a given block is the last one can be easily identified. 

- At signing an external block, there can be different strategies defined, like checking the last block or validating the last couple of blocks. 

- Nothing guarantees that the external external block are stored. As it is on the one hand an advantage, because this way old information can be deleted, it is a drawback as well, because nothing guarantees that the old blocks are actually stored. 

- There should be a mechanism that guarantees that the given last nodes are stored somewhere. This mechanism must crash fault tolerance, but not necessarily Byzantine, because based on the block proofs it can identified if the block is valid.    

- The storage mechanism and probably the whole infrastructure as well must be supported by a cryptoeconomical incentive mechanism. 

- The algorithm should have an economical incentive mechanism that slashes or discourages nodes signing more than one blocks on a round.

Creating off-chain proofs in blockchain protocols

Considering a blockchain protocol, it can be sometimes useful to have a proof that a certain transaction or state was applied to the blockchain, without actually involving this data in the blockchain. Such a structure can be realized by distributed ledger solutions where the identity of the nodes are well-known. One algorithm might be that miner or validator node creates a private - public key pairs as identity where the public key is written into the blockchain but the private key is kept secret. If a piece of data is signed by the private key, it can be made sure that this piece of information was in fact validated by the protocol. The algorithm might be fine-tuned and further improved in a way that not only a leader node signs the piece of data, but many others as well, like in case of a quorum consensus or at a two phase Nakamoto consensus, like at Tendermint. The piece of information can be assigned by a timestamp as well, in the sense of validating the exact block where the information was signed. It can be realized as generating a new identity, new private public key by the validator nodes at each round only for the given round. 

Creating a blockchain algorithm that can not fork

Creating a blockchain algorithm that can not fork is actually not so complicated. What we need to have is a mechanism to make sure that we know all of the miners or validators in the system. This might be a special transaction that can be initiated by a node that wants to join. This special transaction is mined or validated in a standard way and added to the list of  active miners or validators that can be stored in the ledger in part of the on-chain governance. 

After that the blockchain consensus algorithm has to have two rounds:

1. with the help of a Nakamoto consensus the next block can be found, however this block is still not applied to the state. The block is considered as a proposed block at first. 

2. The proposed block must be signed by more than 66% of the active nodes to be considered as valid and be applied to the state. Certainly, such a signing and voting process is not something that can necessarily efficiently realized on a global scale considering many active nodes. 

3. Last but not least, a deleting voting peers mechanism can be built in a garbage collection style. If a node do not have active vote for a long time, it can be considered as it has already left the active miner or validator nodes. 

The algorithm can guarantee the working mechanism without forks, as in case of a network partition there would not be enough votes for a given block. Certainly, there is no magic, in such a case, the network would simply stop working. We simply prefer consistency against availability in case of network partition, according to CAP tolerance.  

Notes on the strengths of the cryproteconomical guarantees

Cryptoeconomical guarantees are actually weaker than the pure cryptographical ones. Cryptoeconomical guarantee means that hacking the system is not profitable, meaning that more money will be lost than gained. As an example proof of steak is based on such a cryptoeconomical guarantee, that states that if I want to hack the system and it become well known you lost all of your stake. As it is a logical motivation that most of the people or rational actors behave economically rational, meaning that they tend to maximize the profit or benefit in some sense. However, the problem is that most of the economical guarantees exist only in the system itself based on assets and resources that are defined by the system itself. So, it is certainly if I try to hack the system in a proof of stake I will loose my stake, but perhaps I my economical rational profit maximization is not based hundred percent to the systems itself. As an example, if the hacking attempt will be well-known, the general trading value of the platform against like USD might fall, that means that I can make a profit from shorting and I might as well do profit even if I loose my stake. 

On the contrary cryptographical proofs use another scarce resource, which is usually computation. Simply put, most practical cryptographical algorithm assumes that breaking the algorithm is computational infeasible meaning that it would take millions of years even with the most advanced, state of the art computers. This is a kind of practically impossible guarantee which is much stronger  than a not profitable one. 

As a consequence, a cryptographical or computational guarantee is always stronger than a simple cryptoeconomical one, mostly because economical rationality can be interpreted only in the system but in general economical rationality is something more complex. 

Perhaps it is important to note though that proof of work is actually an economical guarantee not a cryptographical one, because the amount of computational power to break the consensus does depend on the competition of the miners. With other words, it depends on the amount of money invested to mining equipment.   

Notes on multi block algorithms and protocols

The research of the decentralisation is focusing pretty much at the moment for the scalability of different protocols and platforms. Bases on the current research directions, there might as well efficient blockchain protocols in a couple of years. So, we might as well investigate the possibilities of creating algorithms and protocols that can not e executed in one block or one transaction but can only be realized by several actions, crossing several blocks. Actually, layer 2 protocols, like lightning network or raiden are going a little bit in this direction. Multi block protocols can provide many services that are not imaginable with current one block architectures. 

How to create native external oracle with Nakamoto consensus

Similarly to the previous blog desisgning a decentralized native external oracle can be realized in a same way as a native random oracle. The principle is basically, the same: on the one hand the miners or validators measure the external data sources and put them into blocks or at least temporal blocks. On the other hand, imported data should be kept in secret, because otherwise new miners could influence or even hack the algorithm itself. 

The full multi-block native external oracle algorithm can be described as follows:

1. An imitator having a {Priv, Pub} private and public key pairs creates a external oracle request that includes the pubic key as well:

request_extern (Pub, N, ext)

, where Pub is the public key of the requestor, ext is the external data source and  N is the number of round during the external data source has to be measured.    

2. At mining or validation, a miner or validator measures the value of the external data source that is encrypted by the public key of the reqestor and put at in the request itself. So after the first validation, the request will look like:

request_extern (Val1)(Pub, N-1, ext) 

where Val1 is the measured external data encrypted by the public key. To ensure security Val1 value should be put into the blockchain as well, not necessarily forever but at least during the N phase of execution of the native external oracle. So with other words, the request would be splited into two parts:

request_extern (Val1) 

will be written into the blockchain

request_extern (Pub, N-1,ext)

can be available as a new transaction request that is propagated throughout the network in transaction pools, waiting to be mined or validated. Similarly, after k<N rounds, there would be k encrypted external values in the blockchain:

request_extern (Val1)

request_extern (Val2)

...

request_extern (Valk) 

and a new request as a transaction which is 

request_extern (Pub, N-k, ext)

3. After N rounds, the requestor can aggregate the external values and decrypt them with the Priv private key. 

Ext1 = Decrypt_Priv(Val1)

Ext2 = Decrypt_Priv(Val2)

...

ExtN = Decrypt_Priv(ValN)

The individually external values should be aggregated in a way that the they provide a correct average value even if some of the nodes try to hack or game the system. The algorithm should contain an incentive mechanism as well, giving a reward to nodes that gave correct values in this way motivating nodes to produce correct data, providing a Schelling point as decision making algorithm. Supposing that around one third of the nodes and measurements can be fault, we can have the following algorithm:

a. filter 33% of the most extreme values
b. make an average of the rest that remained providing the real external value
c. reward the nodes whose values were not filtered out based on the distance of the average.

The algorithm has unfortunately some performance issues: It takes N rounds to find out a real decentralized external value. This can be pretty long and pretty costly depending on the given blockchain platform. Considering a Nakamoto consensus the algorithm is pretty difficult to speed up, as the basic idea is that the external values are comming from N individual different sources that actually means at a Nakamoto consensus N different blocks. This implies the fact as well that the data source should keep the value for a long-enough time, like preserving the same value for hours. The algorithms can not really be used with fast-changing data sources.   

A further question can arise how the data exactly used like within a smart contract. As private keys should not be stored in the blockchain, there should be an additional round with the wallet software to encrypt and aggregate the information which might introduce elements of unnecessary centralization and difficult to build in directly into a decentralized smart contract. It is important to note however that this private key is not necessarily the same as the private key of the account so it can be actually revealed as soon as all the N nodes created a guess for a random number. As a consequence a second transaction can be used to calculate the real random number, like:

evaluate_extern (Priv)

At this moment the private key can be published to the blockchain and the evaluation algorithm can be implemented with a smart-contract in a decentralized way.

From a practical point of view a smart contract with built-in native external oracle would look as:

function with_ext (input params) return (output params) {

   ...

   variable ´= External(<external_datasource>);

  ...

}

for evaluating such a smart contract, there should be two transaction used:

- the first one would call the function with a public key of the external oracle making the initialization in the external data measurement.

transaction init with_ext pub_key_ext

- the second transaction would publish the private key and make the whole evaluation and the execution of the rest of the business logic, like:

transaction exec with_ext priv_key_ext

The proposed system has unfortunately one denial of service attack possibility. The one who initiated the external oracle has the private key and can calculate the result previously. If this result does not make benefit for him, he choose not to reveal the private key or not to execute the second transaction.  

How to create a native random oracle with Nakamoto consensus

Creating a real native random oracle is one of the holy grail of the blockchain industry. As the problem is not so difficult if the consensus mechanism is a quorum as the nodes participating in the consensus making decisions independently from each other, it is more difficult at a Nakamoto consensus. The problem is with the Nakamoto consensus that the temporal leader creating the next block is practically a "dictator" of the next block and can influence like the random number. The algorithm can be however improved here as well with two ideas:

- creating a real random number is taking several round where several node guesses a random number which are then aggregated at the end. Certainly this is not necessarily a real solution as active leaders might see the previous random values and might influence the next influence in way that is profitable to the nodes. To avoid such a situations we could use the following idea:

- the random numbers are encrypted by a public key of a requestor. As a consequence the next node do not really see the previous values of the previous blocks, so it can not influence the final result.

The full multi-block native random oracle algorithm can be described as follows:

1. An imitator having a {Priv, Pub} private and public key pairs creates a random oracle request that includes the pubic key as well:

request_random (Pub, N)

, where Pub is the public key of the requestor and N is the number of round during the random number has to be generated.    

2. At mining or validation, a miner or validator creates a native random number which is encrypted by the public key of the reqestor and put at in the request itself. So after the first validation, the request will look like:

request_random (Val1)(Pub, N-1) 

where Val1 is the generated random number encrypted by the public key. To ensure security Val1 value should be put into the blockchain as well, not necessarily forever but at least during the N phase of execution of the random oracle. So with other words, the request would be splited into two parts:

request_random (Val1) 

will be written into the blockchain

request_random (Pub, N-1)

can be available as a new transaction request that is propagated throughout the network in transaction pools, waiting to be mined or validated. Similarly, after k<N rounds, there would be k encrypted random values in the blockchain:

request_random (Val1)

request_random (Val2)

...

request_random (Valk) 

and a new request as a transaction which is 

request_random (Pub, N-k)

3. After N rounds, the requestor can aggregate the random values and decrypt them with the Priv private key. 

Rand1 = Decrypt_Priv(Val1)

Rand2 = Decrypt_Priv(Val2)

...

RandN = Decrypt_Priv(ValN)

The individually generated random numbers should be aggregated in a way that the randomness is preserved even if some of the values are not really randomly generated. The exact algorithm here is questionable, but it is important that the original entropy of the requested random number is maintained even if some of the nodes are cheating. Ideas might be:

sha256(Rand1, Rand2, .... RandN)

sha256(Rand1 xor Rand2 xor ... RandN)

sha256( ... sha256(sha256(Rand1))... )

  

The algorithm has two drawbacks that can be fine-tuned on a long run: 

- The algorithm takes N rounds to find out a real decentralized random number. This can be pretty long and pretty costly depending on the given blockchain platform. Considering a Nakamoto consensus the algorithm is pretty difficult to speed up, as the basic idea is that random numbers are comming from N individual different sources that actually means at a Nakamoto consensus N different blocks. 

- Based on the evaluation algorithm we should assume that some of the miners or validators created a good random number. Consider a good byzatnine evaluation function at the end even if some of the nodes cheat the resulting random number can be a good one, like cryptographically secure. The problem is however that even the hones nodes are not really incentivized to create good random numbers, hence we can not really measure or punish if nodes produce good random numbers. It can be certainly an assumption that certain number of the nodes are honest, but actually it would be much better to measure and validate this fact. 

A further question can arise how the data exactly used like within a smart contract. As private keys should not be stored in the blockchain, there should be an additional round with the wallet software to encrypt and aggregate the information which might introduce elements of unnecessary centralization and difficult to build in directly into a decentralized smart contract. It is important to note however that this private key is not necessarily the same as the private key of the account so it can be actually revealed as soon as all the N nodes created a guess for a random number. As a consequence a second transaction can be used to calculate the real random number, like:

evaluate_random (Priv)

At this moment the private key can be published to the blockchain and the evaluation algorithm can be implemented with a smart-contract in a decentralized way.

From a practical point of view a smart contract with built-in native random oracle would look as:

function with_rand (input params) return (output params) {
   ...
   variable ´= Rand();
  ...
}

for evaluating such a smart contract, there should be two transaction used:

- the first one would call the function with a public key of the random oracle making the initialization in the secret random numbers.

transaction init with_rand pub_key_rand

- the second transaction would publish the private key and make the whole evaluation and the execution of the rest of the business logic, like:

transaction exec with_rand priv_key_rand

The proposed system has unfortunately one denial of service attack possibility. The one who initiated the random oracle has the private key and can calculate the result previously. If this result does not make benefit for him, he choose not to reveal the private key or not to execute the second transaction.