[Cryptography] Proof-of-key blockchain

Camille Harang mammique at garbure.org
Mon Aug 21 16:06:57 EDT 2017


Hello everyone. I've been thinking about a light alternative
proof-of-(work/stake) algorithm for blockchains that doesn't imply
hardware/electricy race. I'd like to request for your comments about it.

The reason why such exponential investment is made into this
hardware/energy is because it is proportional to the chances of winning
the proof-of-* race. The proposed algorithm to avoid such a race is to
determine the winner before the race starts, with almost zero CPU power
needed to discover its identity.

Let's consider that an arbitrary amount of coins have been pre-mined and
sold to fund the development (e.g. 5%). In order to get a chance to be
rewarded with newly mined coins and fees for discovering a new block, a
node needs to have one or more reward-keypair(s). Such reward-keys can
only be buyed/registered on the blockchain, its price must be set to at
least the current number of coins rewarded for discovering a new block,
let's say 50 coins for the first years, like for Bitcoin (1).

Buying/registering a new reward-key on the blockchain is like buying new
rig hardware, the more you have on your node, the more you increase your
chances to win the race (2). For every node to unanimously agree on the
winner, they all need to work on the very same block of transactions, I
explain later how I think this goal can be achieved. Then, a simple
checksum hash needs to be computed by every nodes on the new block, it
is made of the previous head block's nonce appended by the ordered sum
of outgoing transactions' addresses (3), it must have the same length in
bits as the pubic-reward-keys (e.g. 256 bits), the public-reward-key
that is the closest to this hash is the winner (nearest neighbor
matching like with LSH). The node that happens to be the winner (who
owns the corresponding private-reward-key) has to claim the block by
signing the totality of its data (block's head index on the chain,
ordered transactions in full, plus its reward transaction) and broadcast
its claim for other nodes to validate and add it to their blockchain's
head (4). If the block is not claimed, it can be for multiple reasons,
blockchain fork (nodes not working on the very same block of
transactions because of accidental or malicious cacophony), network
latency, or simply the wining node being down. But I think these cases
can be dealt with securely, as explained below.

In order to be sure that every node of the network is working on the
very same block of transactions at the very same time, some rigorous
synchronization has to be set up, with carrot and stick for the
participating nodes. First thing is to prevent transactions from being
constantly broadcast, otherwise because of propagation delay the data of
the new block would always be in an inconsistent state among the
different nodes. As the delay for having data propagated to 99% of a P2P
network (Bitcoin) appears to be about 40 seconds (4), I propose an
arbitrary "pulse window" of 20 seconds for nodes to initiate the
broadcast of their transactions (they need to synchronize at startup via
NTP), followed by 40 seconds of retention of new transactions (meanwhile
new transactions are being queued in each node, waiting for the next
pulse), for letting the time of all the transactions to reach the
totality of the network. So, there is one broadcast pulse every minute
(20+40), as well as one new block. If any node do not play the game
(wrongdoing, miss-configuration, bad QoS, etc.) that triggers cacophony,
the network will have to identify and ban them (5) at the next pulse. On
the other hand, nodes that provide good synchronization, QoS, etc. will
be rewarded by receiving a part of the fees of the transactions that
they have initially broadcast. To do so, transactions and their entry
node need to identify each other reciprocally. Each transaction
identifies the entry node chosen for broadcast, as well as the node
signs the transaction (or preferably a whole transactions' batch in a
single network packet). Node identification is done via one of its
reward-key(s).

If some transactions are sent too late, not reaching the totality
(99.9%) of the network (likely to be initially broadcast around the 55th
second, just before the end of the 20+40 seconds pulse (4), instead of
the dedicated initial 20 seconds pulse window, because of intentional
cacophony malice, or miss-configuration, bad QoS being more unlikely for
such a long lag), then the blockchain's working head will be forked into
multiple heads. Therefore, the probability of finding the next block
will be divided by the number of different forked heads (proportionally
to the respective number of nodes working on each forked head). Let's
take an arbitrary case scenario where the blockchain gets forked into 3
equally distributed heads, each representing 33.3% of the nodes, the
respective chances to find each of these 3 different forked blocks is
divided by 3 (for each forked head block there is a 66.6% chance that
the winning reward-key is working on another block, therefore won't
claim it). Thus, after 2 or 3 iteration pulses (or even only one), the
entirety of the network will find the block discovery/validation rate
dramatically drop, which will trigger nodes to enter "cacophony mode",
stopping to emit transactions, and broadcast the blocks they are working
on after the cacophony was detected (and maybe one or two blocks before
that as an uncertainty margin), as well as the signature of the block's
hash by the node (6). After few seconds/minutes, all the nodes will have
gathered a reference copy of all different versions of blocks being
worked on, along with the number of times they have been signed (a.k.a
in which proportions a specific version of a block were spread amongst
the network). All nodes now have an accurate snapshot of the total
topology and consistency the network, few blocks backward from the
blockchain's head, before the fork happened. Then nodes can
independently compare blocks, whitelisting every nodes that had their
transactions registered on every blocks (meaning they were broadcast on
time), baning those that are on some blocks but not other popular ones
(7), therefore the network self-heals by purging bad nodes, and resume
mining by rolling back to the last block that was mined before the
cacophony started.

In the case of a node suspecting cacophony because being in the fringe
of the network or out-of-sync (thus not receiving transactions on proper
time), other nodes won't be in "cacophony mode", so the node will find
itself lonely by not receiving any/enough different block versions
(along with their signed hashes), therefore it will know that there is
no cacophony, but bad QoS or configuration, this will need to be fixed
by resync NTP, re-configure, change peers, sys-admin intervention, etc.
They'll have to catch up quickly not to miss the race/reward.

In the case of a block not being claimed because of the winner node
being down, the network would enter in "cacophony mode" as well, but
figure out that it is consistent, therefore simply blacklisting the
winning public-reward-key of the unclaimed block, until it gets unlocked
by a dedicated "unlock message", signed with its corresponding
private-reward-key when the node gets back online.

There might be plenty of smaller/bigger flaws that I did not think
about, I'd like to request for your help in identifying and hopefully
fixing them. I've been thinking that rich wrongdoers could escape the
carrot and stick policy constraint by buying reward-keys with the only
goal to prevent the network from taking off, provoking endless
cacophony. I think this can be fixed by adjusting the price of the
reward-keys over time (1), or even using a non-mandatory collaborative
blacklist system for the early stage of network growth, until the price
of reward-keys becomes dissuasive for a performing real prejudicial
sabotage, even for rich wrongdoers. Also, because there is no CPU
constraint for calculating blocks, it would be easy for anyone to forge
a longer chain, however I'm not sure that the longer chain policy is the
best here, and such forged chains could be easily detected because of a
too much redundant winners' identity (not representative of the global
reward-key pool), and not to mention that it cannot be broadcast as
nodes do not get new blocks from the network but calculate them internally.

What do you think?

Thanks,

Camille.

(1) Price for buying/registering a new reward-key cannot be lower to the
number of coins rewarded for finding a block to prevent their number to
be exponential, but it could/should be higher to prevent rich wrongdoers
to buy many and use them to disturb the network, it could also maintain
the size of the network to a consistent state. Here we take the example
of 50 coins per reward-key, which means one every minute, one every few
hours sounds more reasonable and manageable, but this is outside of the
scope of this post.

(2) A special transaction has to be done for purchasing a reward-key,
unlike when simply spending coins with outgoing/incoming wallet address,
here you send your self-generated public-reward-key (needless to say
while keeping the private key private) along with your 50 coins, in
return the network makes the 50 coins available again to miners as a
reward for the next block discovery, and register your public-reward-key
on the blockchain. The reverse operation to destroy the reward-key for
getting the 50 coins reimbursed should be possible, as well a replacing
a reward-key by a new one if suspected by the owner of being
corrupted/stolen. The 50 coins given when finding a new block (or being
reimbursed) are made available again from a previous purchase(s), or
newly created if this coin reserve is empty. The available monetary mass
may inflate or shrink depending of the market demand for reward-keys
(mining) or liquidity, this policy can be discussed and algorithmically
adjusted/limited in the specs (e.g. coins made available again after
buying rewards-keys cannot represent more than 10% of the minted coins).

(3) We use outgoing transaction's addresses because they cannot be
forged on-the-fly to alter the resulting hash. If we use the full
transaction for calculating the "winning hash", nodes could try to forge
and inject one transaction at the last second, playing with decimals to
get the closest result to one of their public-reward-key, which would
incite again for a hardware/electricity race.

(4)
http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf

(5) Quarantine duration should be incremental for each ban, e.g.: 3h,
12h, 72h, 2 weeks, 4 months, one year, etc.

(6) Any node signing more than one different block for the same head
number will be banned (5) and its data ignored.

(7) In "cacophony mode" marginal blocks that are not widespread and
lacking transactions number should be ignored, they are more likely to
be on the fringe of the network, not having received some transactions
on time because of QoS-like issues.



More information about the cryptography mailing list