Proof of Nearest Consensus Protocol_en
By Fabio Gómez
E-mail: ceo@wagerchain.org
Updates: https://github.com/WagerChain/PoN/wiki
[PDF version (ES)]
Proof of Nearest (PoN) is a consensus proposal that allows the creation of an efficient, neutral, secure and permissionless network with low cost and freedom of participation, where the computing power and the greater economic capacity are not relevant. As initially proposed by Satoshi Nakamoto in his White paper, PoN seeks to rescue the concept of "1 CPU = 1 Vote", but also to resist mining pools, hashrate rents in the cloud and the advantage of a greater computational force of ASIC / GPU / FPGA. PoN generates entropy in the selection of the constructor proposing a new mechanism of "random election" and is the result of a "competition" where each block generates a challenge that becomes exponentially more demanding as the participation of nodes grows. Each node exists in the network as a single node, has the same opportunity as each other node and can not join forces with others to favor its choice as a constructor. No node has a minimum requirement of resources; simply if they are not enough, may or may not achieve to perform the task that in turn, allow you to participate by being the next constructor of the block. If you do not succeed, complete the task out of time, continue helping to secure the network permanently and seeking effective participation in the following blocks. It has high transaction capacity (TPS) to cover the current demand for more. The flexibility of PoN allows to continue scaling dynamically at the same time that advances in connectivity can increase the speed of propagation in the network. The short block construction times in PoN and the multiple incentives allow a greater distribution of reward among the miners. The flexibility, incentives, ease of participation, resistance to clusters and low cost, encourage the existence of many more nodes than any current network.
The concept of PoN can be partly adapted to optimize other existing blockchain like Bitcoin without it having to abandon PoW, but making it much more efficient achieving significant energy savings. This solution is proposed in a separate document.
With each blockchain project that is born, new challenges also arrive with specific needs that contribute to improve their use, increase applications, and encourage the adoption of technology. For our specific project, it is inherent to guarantee:
- Processing of all transactions
- Construction of blocks in fixed periods
- High transaction rate
- Massive participation of nodes
This implies that when the block duration is set, the size is dynamic and all transactions in that period must be validated and processed. If a transaction is not processed, it is not queued and must be sent again in a later period.
Our challenge was to find an efficient and safe alternative solution that encourages the existence of a large distributed public network, resistant to groupings, and where there is absolute decentralization. Main challenges to consider:
- Propose an effective solution to the problem "Random Leader Election"
- That requires low computational capacity
- That does not allow adding or grouping opportunity
- Make it easy to participate. Without votes, delegations, etc.
- That does not depend on specific HW (ASIC / GPU / FPGA / CPU-SGX)
In short, we want to preserve the spirit of competition proposed by Nakamoto with PoW but without computing force. No possibility of power concentrations for computational, economic or delegation capacity as in PoS and DPoS. Solutions for improvements such as ProgPoW are aimed at resisting ASIC devices but fail to open the door to massive participation from common devices such as CPUs. Other alternatives such as PoET are tied to the use of specific hardware such as Intel® SGX, which also hinders participation. PoN could be understood as an alternative to these solutions with great participation flexibility. We will understand it later.
Game theory is still a determining factor. The method must achieve the equilibrium of Cournot and Nash by having all participants assume the same strategy and ensure that the convenient honesty in the network prevails to have their best benefit. PoN gets it!
The integration of the method "PoN as Random Leader Election for Blockchain Systems" that I briefly explain here and delve into in another document, guarantees entropy fulfilling the necessary conditions:
- Termination: The election must end in a finite time.
- Uniqueness: There is exactly one leading node
- Agreement: The other nodes know and accept the leading node
In addition, it considers very favorable characteristics for permissionless distributed networks where the nodes enter and leave the network permanently.
- Size: The method does not need to know the size of the network
- Topology: Fits any network topology
- Communication: Minimum information exchange
- Difficulty: The method throws a condition proportional to the existence of nodes that increases the difficulty for an attacker.
As in PoW all the nodes have a same challenge although some can complete it faster than others due to their computational strength, in PoN they all also have the same challenge, but only one way of solving it, the computational force being irrelevant. However, the concept of difficulty is maintained, which in turn increases with the increase of nodes that carry out this challenge. The task is unique per node / block and neither can join forces to reduce the difficulty. To make resistance to many replicas of different nodes under a single control, technical and economic restrictions are added. The existence of nodes is limited by public IP and a formula estimates a value in the native currency that must exist for a previous period and without movements, as proof of belonging. A new standard script can be considered as pay-to-enabler to create a specific UTXO for that purpose. We will call it "enabling UTXO".
With PoN any user with any device (including CPU's) can be part of the network simply by having their UTXO enabled and running the service on their computer. The miner will have available to spend his enabling UTXO while he is honest, and may also participate continuously or for periods of time such as working hours for example. Spending your enabling UTXO only means that you can not claim if you are favored in the competition, losing the opportunity to be a builder and therefore your reward. To return to the network, must deposit to your address and wait for the time required. Pausing your participation a few minutes, hours or days implies that you do not process your "task" and therefore you are giving up the opportunity to be the block builder during that time. You can restart your work at any time and continue to participate normally.
The PoN protocol introduces new features adjusted to the need of our project, but some can be adopted or not, according to individual requirements.
| Feature | Description |
|---|---|
| Transactions: | In the current protocols, transactions are selectively collected. If the blockchain solutions want to surpass the current centralized payment systems, all transactions must be made equally important and processed without priorities. For our solution this characteristic is mandatory. |
| Block duration: | In the PoN protocol, the duration of each block is fixed. The mining period must be parameterized and can range from seconds to minutes, but ensuring the minimum time required by the protocol to guarantee the synchronization of the nodes in collected transactions. |
| Consensus: | Our mechanism requires a job that ensures the network, with the same opportunity for each of the participating nodes. PoN generates a block constructor in a totally random, unpredictable and unmanageable way; only between the nodes that are active and processing the transactions. |
| Reward: | Rewards have more distribution. Given the high participation of nodes, the rewards do not have to be high and the cost of sustaining the network is reduced. In our project blocks are estimated every 5 seconds and this equals 17,280 * rewards every 24 hours against ~144 in Bitcoin. |
| Participation: | There will be as many miners as no computing force is needed, and the reward opportunity is real. They can enter, exit or pause mining at any time. Nor can they join forces to act as one by breaking the mining pool and forcing them to participate as fully independent nodes. |
* There may also be a multi-reward method involving mediators.
The PoN algorithm is based on a geometric distance calculation between two points located within a four-dimensional space (4D). Each node will have a different but deterministic result of this calculation and with this it will participate in a competition that will throw the constructor node. The node that calculates and claims with the least distance will be the constructor.
This distance represents an inverse proportionality with the number of participating nodes and is understood as a threshold of difficulty for the other nodes. If the claim universe is from 0 to a maximum distance D, the minimum expected R-claim for n nodes is:
Keep in mind that you do not need to know the number of nodes participating and not everyone to report the result. Each node claims only if its calculated distance is less than the claim threshold and is less than the current minor claim. Technically only 20 claims are needed to choose a winner out of more than 1 million participants. The 1st claim disqualifies 500 thousand nodes, the second disqualifies another 250 thousand, the third disqualifies another 125 thousand, etc.
If we call n the possible participating nodes and q the number of claims, then for q = 20 we have to:
This does not limit the number of claims received. Many more can arrive due to the necessary times so that each node knows the smallest current claim.
The first point (P1) is obtained from the component x of its public key K <pubKeyHash> that identifies it and will be permanent during its existence as a mining node in the network. This key must be the same from where the reward claim address was derived and where the enabling UTXO is located. This component of the key has a length of 256 bits which will be divided into four portions of 64 bits each. In strict order, each portion will be the coordinate of each of the four axes of the tetra-dimensional space x, y, z and w respectively. The crossing of coordinates within the tetra-dimensional space defines (P1).
Ex. Address: b525f289fc9f17a1d9a18d4d18440f0850c4fc938c38e871a6a5bdd781dfa039
Coordinates: x1 = b525f289fc9f17a1 y1 = d9a18d4d18440f08 z1 = 50c4fc938c38e871 w1 = a6a5bdd781dfa039
The second point (P2) against which the distance or proximity will be calculated, will be defined by the hash resulting from the SHA256 calculation on the block under construction that will include its same node address in the reward transaction. A unanimity protocol yields only one form of block construction. This resulting hash is subjected to the same previous treatment by dividing it into four portions of 64 bits each, which will be the coordinates corresponding to the x, y, z and w axes respectively of the point (P2).
Ex. Resulting Hash: 6d29e07e097ae9f175d54f10124484e8d4d0a820cf795aa05ed8095eed1f9de5
Coordinates: x2 = 6d29e07e097ae9f1 y2 = 75d54f10124484e8 z2 = d4d0a820cf795aa0 w2 = 5ed8095eed1f9de5
To make this calculation we rely on the basic principles of geometry (Pythagorean theorem). However, the resulting distance with which the claim is made will be expressed as the square of the real distance (nd2). This is for the purpose of being able to deliver binary integers, since calculating the square root would imply binary fractions that are not convenient in the expression. However, although the result alters the proportions, it retains the strict order in the proximity competition that we are carrying out.
To facilitate the concept this exercise is exposed as an example in a two-dimensional plane (2D), 8-bit public key and coordinates of only 4 bits:
Now, we can detect that a node whose address places it closest to the center of the tetra-dimensional space, would have more opportunity than a node whose address places it near one of the "edges" of said space. To compensate for this, and for all nodes to have exactly the same possibility, the space will be replicated in each of its faces, edges and vertices so that the node performs the calculation from all the points of all the spaces. For example, if it were a two-dimensional space, we would need to replicate 3^2-1 = 8 times the space.
In this way for a four-dimensional space (4D), a total of 3^4-1 = 80 replicas will result from which the calculation must be made.
The work of the miners is to perform a unique task every time a block is being built. In this work, the direction of the miner is very important since it fulfills several functions.
- It is the address where it is deposited and proves the membership of the enabling UTXO to be able to participate.
- It is the payment address where the rewards will be deposited.
- It is the only information that the other miners will use to verify that it is the constructor and validate the block.
- Define a constant within the mathematical process of the competition.
- It will be associated with the IP address in the tables of the other miners.
Each participant miner must perform the following procedure to validate a block. The time for validation can be extended up to several blocks ahead depending on the time necessary to achieve the necessary synchronization of the network. These are the steps:
- Have the enabling UTXO at your address (and for the time required).
- Validate all the transactions of the block period and generate their respective hashes.
- Reorganize the transactions in strict ascending order of hash and check unanimity on the resulting Merkle root. A protocol ensures this unanimity among all the nodes.
- First add the reward transaction to your own address, and recalculate the Merkle root.
- Construct and calculate the hash of the header that includes the previous hash and the previous claimant nd2 distance. The only difference should be the Merkle root because it contains a different reward transaction for each node. There is no NONCE.
- Calculate the result nd2 using PoN.
- Only if nd2 is less than the current minor claim, apply to the delegates as the new "constructor".
- After closing the claim period, a unanimity protocol confirms to the network the smallest distance nd2 reached.
- Rebuild the block with its own transactions in memory including the reward transaction to the address of the node with the winning claim.
- Recalculate nd2 (with constructor node P1) and if the result corresponds to the claimed nd2, the "existence of the enabling UTXO" is validated, and then the block goes to the chain becoming true for each one of the miners who validated
- If the result does not correspond, the next smaller claim is validated successively and the fraudulent claimants are punished by including them in the blacklist.
It should be noted that this very simple process, brings together the best features of the current protocols creating a task and competence as in PoW, and solving the challenges in the participation of PoS. It also guarantees total decentralization without delegations of power or voting processes like DPoS. A miner with economic power can only increase his income by creating many nodes that in turn secure the network and increase the difficulty in the competition. An ASIC will be a real waste of capacity, the mining pools do not make sense as it is not possible to send the funds to an administrative address that would be different from the own one, and the mining farms are not viable since there is no need to have hashrate or there are any way to show that the contracted work is being done. The only viable option is Cloud Computing, which also turns out to be beneficial, as can be understood later on.
The result nd2 of thousands of processing by thousands of honest nodes, also yields a numerical result that increases the difficulty for someone who wants to ensure having the builder node under his power. Mathematically it is a result of chance where the 50% probability of reaching the shortest distance can only be achieved by having an equal number of nodes than the existing honest ones even if they are not known. This implies that having 50% of the nodes in the network, only means 50% probability of being the constructor of a block; and if we think about insuring, say 3 continuous blocks, this probability decreases to 12.5%. However, this would only give possibilities to be the claimant but it does not allow to manipulate or eliminate any transaction as we will see in the unanimity protocol.
Since the spirit of PoN is to completely eliminate the opportunity that would give more computing power, the miners could look for other alternatives that would increase the probability of obtaining the reward for closing a block. One of these alternatives could be to create many virtual machines (VMs) within a single computer. In theory, it should not matter if we think that n virtual machines are really acting as n nodes that in turn are helping to guard and verify the information independently. They are also contributing to build more proximity results that make the challenge more difficult for an attacker. However, this would affect the possibility of the nodes that carry out the process from single computers in the home or office and again the democratic spirit of PoN would be lost. To avoid this, the first step is to limit the number of nodes under the same public IP address. And second, without becoming a proof of stake, demand the existence of the enabling UTXO that fulfills important functions.
This output transaction is built with a special script that identifies its function and enables spending restrictions. If the address that contains it is included in the blacklist, it will be blocked temporarily or permanently. The spend of an enabling UTXO only becomes effective after N blocks. This in order to extend the period of inclusion in the blacklist if it is detected as a fraudulent node. We will see the importance of this restriction in case of an attack. The balance in an enabling UTXO can be fixed or be considered dynamically according to the threshold thrown by the number of participating nodes. In any case it must be a huge investment with risk of loss for a possible attacker. The existence of enabling UTXOs also functions as a metric of nodes and value supporting network security.
Each node is obliged to stamp the reception time with its own clock, verify the account, the signature and validate the requested transaction before propagating it to its connected peers. You must also send the hash of the transaction directly to the mediating nodes that are processing the unanimity protocol.
The design is oriented to collect all transactions and a protocol defines unanimity and order in the construction. This limits the search for more opportunities by changing or combining the amount and/or order of transactions collected. In PoN there is no NONCE and although each node builds the block independently, the only possible difference is its same reward transaction that is also constructed in a single way.
Each node will be obliged to validate each of the transactions since it does not receive the complete block and, instead, must be sure to obey the unanimity protocol to build the same block as the other nodes, otherwise an invalid claim will be made temporarily freeze or lose your enabling UTXO. Each reward claim is only made by reporting its own address and the claimed distance to the nodes that are processing the unanimity protocol. In this way, the other nodes can not receive a block or fraudulent transaction since with the same transactions collected independently, will build the block again adding the reward transaction of the claimant, processing it and verifying that the distance claimed is correct. If everything coincides, it becomes a valid block within its chain.
Since the block duration periods are fixed, it is evident that the size of the block must be dynamic. The question is: Up to what size?
PoN has a great advantage and is that the process of building the block can be done in very small times, generating small blocks in turn. Without taking into account the necessary propagation times (which we will see in Block Times) let us think that technology allows us to easily build an 8 MB block without major problems and for our case, this can happen every 5 seconds. For Bitcoin, the basic transactions occupy between 200 and 500 bytes depending on the number of addresses involved. Let's assume the greatest value and we estimate that:
This value of 3,355 TPS far exceeds Visa's current effective transaction rate estimated at 2,000 TPS. So PoN guarantees by far the high rates of transactionality that are demanded today as a payment channel, and also has the capacity to scale dynamically being maintained by the nodes that have the necessary resources to meet that demand. This encourages other nodes to improve their connectivity and storage resources without excluding them from the network at any time. All this happens without any need to update in the code.
The times must be parameterized initially and can range from seconds to minutes. Short times can provide greater efficiency in TPS with smaller blocks and speed up the confirmation time for the user. In our project we also have the need to generate hashes of block closures continuously. It should also be considered that the advances will provide in a very short time the facility to create blocks in very short periods, maybe a millisecond. For now we have to focus on having the necessary time to get the synchrony of the network and unanimity in the transactions listed to process in each block. Recall that all nodes must reach the same Merkle root of the transactions to be processed before including the reward transaction itself. PoN has estimated three time lapses within each period to assign them to a task each: Synchronization, contest and validation. It is clear that the validation is the one that requires the least time, followed by the contest where the "claims" will be presented and the one that deserves the most time is the synchronization. For this reason, a percentage ratio is proposed, regardless of the time defined. 80% synchronization, 15% contest and 5% validation. For our initial proposal of 5 seconds it would be understood as follows:
Although the processing is minimal and the nodes have very low computational load, it can also be considered to move the construction and validation of the block more to the future to add time to the synchronization, or even to dilate the time to 2 processing blocks. However, this would add time to the processed transaction confirmation, although it is minimal.
The protocol is executed by 11 nodes that we will call "mediators". It continues to make use of the entropy generated in PoN. Although only a few nd2 distance claims are needed to get to be the constructor, it is certain that a large number will arrive due to the delays that the nodes have in knowing the current minor claim. The nodes that made the eleven (11) minor claims in block n-1, will be the mediators in block n. Among these, a protocol that guarantees unanimity is activated and a table is generated with the transactions to be processed. Upon completion, the resulting Merkle tree is replicated to the network so that each node can validate it against its own root and eliminate or request differences in transactions. Note the entropy in the selection of these 11 nodes as well as the certainty that they are active. There is also no possibility to predict them or to reach prior agreements. The protocol can be executed with fewer participants if the 11 mediators are not integrated. To encourage full participation, it is considered rewarding in the following transaction and/or punishing his absence with temporary blocking.
To prevent late claims from destabilizing unanimity, the eleven mediating nodes also activate a protocol that defines in consensus the valid claims among those received within the time limit set for this. These are responsible for replicating the winning distance and the corresponding address to the network so that each one can validate and secure the block.
Although the blocks initially will be very small, when doing the exercise with an estimate to the block limit of 8 MB every 5 seconds we would obtain a result of almost 50 TB per year (ignoring the headers). This is a very high burden for the common nodes to which we intend to facilitate participation.
Keep in mind that this is an extreme calculation. For now it is expected that all nodes can maintain a complete copy of the chain until the load requires a distribution. For this a hybrid model between full and light node is being studied. If in the future a node needs to reclaim space, it will be allowed to store only some specific blocks but keeping the headers of the whole chain. To guarantee a total and balanced distribution of the chain, the fixed existence of the node address in 256-bit format is used. Taking into account the last bits of the address, the node is requested to keep all the blocks whose hash, also ends in the same bites. Just considering n = 8 (1 byte) we already have a distribution of 2^8 = 256. Which will greatly reduce storage.
This supposes some other requirements of the model like selecting pairs by complement and not by proximity or by latency, immediate exchange of transactions in history, etc.
In theory, there should be no forks except for a network isolation that is unlikely. However, a solution must be considered. Since the block periods are fixed, there will be no longer chain in case of a fork and no longer a proof of work. On the other hand, it will be possible to know which chain has been validated by more nodes estimating the algebraic sum of the resulting claim distances (nd2) since the fork. The claim distance of each block is part of the header in the subsequent block. The shortest sum will be the valid chain. The more honest nodes validating, the distance of claim (nd2) will be much smaller being much more demanding for an attacker to overcome this requirement.
Considerations open to discussion with the community.
The protocol eliminates the power of adding the opportunities under a single node to the blockchain as in PoW. In this way everyone will be required to operate as independent nodes and this will increase the number of mining nodes in the network. If they wish to share profits, they must do so under agreements outside the network and with external mechanisms of trust, since the reward will reach the only address of the claiming node and possessor of the enabling UTXO. In addition, the mechanism of payments distributed in short periods does not encourage the existence of this type of groupings.
An attack of this type is not viable. In PoN, much more than 51% is needed to dominate the chain. An attacker would have to get at least the six smallest claim distances to manipulate the unanimity protocol by eliminating or altering their transactions. Taking into account that the ease of participation, added to the breakdown of the mining pool considerably increases the existence of nodes, it will be extremely difficult, costly and risky for it, equal and exceed the number of honest nodes. You may even be unaware of the actual number of working nodes since many are only visible when claiming a reward. However they are in the dark working and increasing the difficulty for the attacker. If there were 500 thousand honest nodes, an attacker would have to create +500 thousand different addresses, deposit and create the enabling UTXOs in each of them, wait for the regulatory time and create 500 thousand nodes with different IP.
In edition
Technically an attack of this type aims to isolate a specific user to ensure that the latter has a distortion of the reality of the entire network. It can be used to trick a trade by making it look like a transaction that has been registered in the rest of the network. Thus the attacker manages to obtain for example a physical asset and after stopping the attack, the commerce will see the payment transaction disappear when connecting to the real network. Well, similar to the difficulty that exists in PoW, the PoN protocol maintains a difficulty threshold based on the claims history. If the nodes that are validating this transaction do not meet a claim lower than this threshold, the transaction is not considered suspected.
In PoW a fraudulent node wins the "arm wrestling" and makes its chain accepted without the possibility of rejection by honest nodes. Well, you will never be able to reconstruct the work test of several blocks back to overcome it in length if you are working in the new chain. The attack ends and the fraud was consummated. In PoN an attack is more complex. Technically the attacker faces in quantity thousands of unknown nodes among them but they are a community with the common interest of holding the network secure. Unlike PoW, in PoN the honest nodes detect the attack but they know the transactions of fraud and although the protocol forces them to accept the chain that claims the least amount (if the attacker reached it), they can continue working in parallel on both chains maintaining them until the attack ceases and then return the honest chain leaving the fraud without effect and yes with many balances punished. Keep in mind that honest nodes perform this task for the common interest but without any possibility of agreeing between them. In addition honest nodes build each block from the received transactions and will not accept to delete or alter a transaction that already exists in time for them. In short, an attacker should maintain their nodes indefinitely to sustain their fraud and this would be like usurping control of the network affecting their own interests by taking advantage of an honest and secure network.
This is an initial proposal that can be modified and improved for our specific need. There are also many ways to adapt and take advantage of the concept to improve other existing blockchain.
Proof of Nearest is a totally new method of consensus that solves the problems of delegation getting entropy in the nodes that execute protocols of unanimity and claims but with minimum power of manipulation of the information. It also solves all the environmental and economic cost problems that a brute force work test involves. A PoN network will have many better incentives and flexibility that will facilitate massive participation. The protocol mechanisms added to the high participation, get a more secure network than any other proposal.
R/ Add entropy and generate a convenient length in the result nd2. So came the first idea.
R/ After validating it and correcting vulnerabilities, it will be the basis for the WagerChain project
R/ All contributions are well received and after evaluation, they could be integrated.
R/ We want to build a great community. Write us at pon@wagerchain.org.
R/ Mainly Python.
-
[ASIC]: Application-specific Integrated Circuit
-
[FPU]: Graphics Processing Unit
-
[FPGA]: Field-programmable Gate Array
Copyright ©2018-2019 by Fabio Gómez ceo@wagerchain.org
Holder ID sha256: 9a42d006673d30a3ef4351dfb3b05e04c49e518a254a8253159e177c3b342850
Proof in BTC Tx: 0f9c9a32adc20eea24039c6327a4e611da49c67143d9a022a9882bdffee1394a
This document is dual-licensed under the Creative-Commons BY-SA license v4.0 and the Open Publication License v1.0 with the following license-options:
Distribution of substantively modified versions of this document is prohibited without the explicit permission of the copyright holder. Distribution of the work or derivative of the work in any standard (paper) book form is prohibited unless prior permission is obtained from the copyright holder.