[Cryptography] KissChain

Camille Harang mammique at garbure.org
Mon Sep 11 09:28:31 EDT 2017


Hello everyone, I'd like to present you KissChain, a technical proposal
for getting rid of tedious issues related to proof-of-stakes
blockchains, instead of solving them, by following the KISS principle
(Keep It Stupid, Simple). It is a rework of my previous "proof-of-key"
proposal, which happened to be more like a KISS proof-of-stake. I've set
up a dedicated page, here: https://checkoin.org/misc/kisschain/

Please tell me what you think, and if anyone would be interested in
implementing it let me know.

Thank you,

Camille.


####### KissChain #######

KissChain is a technical proposal for getting rid of tedious issues
related to proof-of-stakes blockchains, instead of solving them, by
following the KISS principle (Keep It Stupid, Simple).

The first issue are the sophisticated but imperfect heuristics used to
workaround network inconsistencies inherent to P2P networks, caused by
accidental or malicious behaviors from participating nodes. KissChain
does not tolerate such inconsistencies, nodes are rewarded for matching
the network's requirements, or banned. In case of inconsistency the
whole network is down, entering "cacophony mode", it is then forced to
identify with certainty bad nodes, ban them, and starts over minting the
chain from where it was before the inconsistency happened. There are no
sophisticated tricks and tweaks to continue minting the blockchain
despite problems inherent to P2P networks, but a strong all-or-nothing
heuristic KISS signal that needs to be dealt with right away with no
mercy by the totality of the network.

The second issue is the selection of blockchain forks candidates.
KissChain blocks are not broadcast to the network, so there is no block
head to choose from. All nodes compute the very same block at the very
same time internally, which is made possible by the requirements
mentioned in the first point.

In order to participate in minting new blocks and receive transaction
fees, nodes need to purchase/register reward-keypair(s) on the
blockchain (1). Buying/registering a new reward-key on the blockchain is
like buying new rig hardware, the more there is on a node, the more the
chances to win new block discovery is high. Where the proof-of-work
secures the network by the physical constraint of computing power, here
it is secured by the physical constraint of having access to a private key.

For each new block, a simple checksum hash needs to be computed
internally by every nodes at the same time, it is made of the previous
head block's nonce appended by the ordered sum of outgoing transactions'
addresses (2), 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 (LSH-like nearest neighbor matching).
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. 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 these cases can be dealt with securely, as explained below.

In order to make 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 appears to be about 40 seconds (3), an arbitrary "pulse window"
of 20 seconds is set up 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 these new
transactions are being queued in each node, waiting for the next pulse),
for letting the time to all the transactions to reach the totality of
the network. Therefore, there is one broadcast pulse every minute (20+40
seconds), as well as one new block. If any node do not play the game
(wrongdoing, miss-configuration, bad QoS, etc.) that triggers "cacophony
mode", the network will have to identify and ban them (4) 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, 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). In a 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 a strong heuristic signal for every nodes, that will
make them to enter "cacophony mode". Then, nodes stop 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 one
of their reward-key(s) (5). Then, 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 the same complete and
accurate snapshot of the total topology and consistency the network, few
blocks backward from the blockchain's head, before the fork happened. No
sophisticated heuristics nor heterogeneous statistical guessing need to
be made here, nodes can simply and independently compare blocks with the
very same algorithm, very same data and find the very same result.
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 (6), 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 entering "cacophony mode" 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 their chance to win a block
discovery.

In the case of a block not being claimed because of the winner node
being down or under DDoS attack (7), 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.
Notes

1) In order to allow initial reward-key purchases, some coins need to be
available at first (e.g. a fraction of pre-minted coins sold for
development funding, or any other solution). The cost for registering a
reward-key must be at least the number of coins rewarded for minting a
new block, in order to prevent their exponential number. This price
should be adjusted between making it dissuasive to register malicious
nodes, keeping the number of nodes large enough for having a really
decentralized P2P network, and small enough for it to remain consistent
(probably a few thousands). A special transaction has to be sent for
purchasing a reward-key, unlike when simply spending coins with
outgoing/incoming wallet addresses, here the node sends it
self-generated public-reward-key (needless to say while keeping the
private key private) along with the coins, in return the network makes
the coins available again to minters as "orphaned coins" for the new
block discovery, and register the new public-reward-key on the
blockchain. A reward-key can be replaced by a new (or predefined) one if
it is suspected by the owner to be corrupted/stolen. New coins being
rewarded or reimbursed should first come from the "orphaned coins pool"
if not empty, otherwise they should be newly created. The available
monetary mass may inflate or shrink depending of the market demand for
reward-keys (minting) or liquidity, this policy should be discussed and
algorithmically adjusted in the specs (e.g. "orphaned coins pool" cannot
represent more than 10% of the minted coins).
2) Outgoing transaction's addresses are used for the checksum because
they cannot be forged on-the-fly to alter the resulting hash. Otherwise
using full transactions 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.
3)
http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf
4) Quarantine duration should be incremental for each ban, e.g.: 3h,
12h, 72h, 2 weeks, 4 months, one year, etc.
5) Any node signing more than one different block for the same head
number will be banned (4) and its data ignored.
6) 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.
7) In case of DDoS attack, the victim node should stop broadcasting
transactions until the attack stops, not to be wrongfully banned for
broadcast lag. In case of block discovery reward, if the price of the
coin worth it, node admins should anticipate such cases by setting up
rescue IP(s) and/or VPN, this foresight might be considered part of the
KissChain QoS requirements. Or, as all nodes compute the same data,
nodes could be cloned with the same reward-key(s), as ghosts or active
nodes, to relieve each other in case of an attack.

Authors
- Camille Harang

Thanks
- Karl Semich
- Natanael L




More information about the cryptography mailing list