[Cryptography] Proof-of-key blockchain

Wed Aug 23 18:13:11 EDT 2017

Hello Karl, thank you very much for taking the time to read an reply.

Le 23/08/2017 à 17:38, Karl Semich a écrit :
> Hi,
>
> Your ideas sound very similar to various proof-of-stake implementations.  Have you looked at proof-of-stake at all?

By proof-of-stake I meant Ethereum-like proof-of-*, that's the only one
that I have studied, it's presented as proof-of-stake and consumes a lot
of CPU. Now I take a closer look I realize that my proposal could fit in
the proof-of-stake definition. The closest idea that have been presented
to me is Algorand, do you know it? It seems much clever and
sophisticated than my proposal. I should be ashamed about that, but
therefore I think that my proposal can have some advantages of the KISS
principle.

> One of the issues of making it cheap to calculate who receives the block reward is that some malicious, motivated user may DoS block reward winners to prevent them from claiming, and control where the rewards go.

DDoS is not enough for that, they need the private key of the node that
they have DDoS in order to claim the block. And they can't forge the
block as the very same block is calculated internally in every node,
blocks are not broadcast (only transactions), the fees and coins go to
the winning block (deposit address is linked to their reward-key, I
forgot to mention that, my bad). DDoS the node would just prevent it to
get its reward, but it can't be given to anyone else. And DDoS needs to
be done very fast, identify the IP of the winning node and DDoS before
it can broadcast a tiny "winning claim" packet, it's a difficult race to
win. In such case node admin would need to have a rescue IP or a VPN for
emergency broadcast.

DDoS on nodes that send transactions would be more harmful, if the
attacker can make it lag for about 55 seconds, it has a chance to fork
the network as the transactions can only reach half of the network in
the remaining 5 seconds, making it loose few minutes for self-healing
from "cacophony mode", and unjustly punish the victim node. In such case
of DDoS attack I suggest the node not to send any transaction until the
attack ends, queuing them, and wait to be back to normal to send it safely.

About the KISS principle of my proposal compared to Algorand I would
they that it gets rid of heuristic problems with an all-or-nothing
approach. Or the whole system works with only one blockchain head, or it
stops functioning in totality until bad nodes are purged if the chain is
forked ("cacophony mode"), and start over where we left off, where there
was only one and unique same blockchain for every node, and keep it that
way. Same for the heuristic detection, tweak, hack and fix of network
latency issues is too tedious, we get rid of the problem by banning
slow/miss-sychronised/malicious nodes, sorry for them, but I think it's
the price to pay to get a all-or-nothing certainty about the network
integrity. People invest millions in designing and producing ASICs for
Bitcoin, asking them for good QoS and synchronization sounds pretty
reasonable to me (and they get paid/rewarded for that). Scaling problem
are addressed by limiting the number of possible reward-keys (IMHO
thousands, or even tens of thousands maximum, but I'm not an expert, it
should be carefully studied and tested beforehand). Sybil attacks are
addressed by the fact that blocks are not broadcasted but computed
internally, so there is no way to contaminate any node with forged
blocks. No democratic voting system with node leaders and Byzantine
agreements as in Algorand, here it's a KISS totalitarian system without
leader, nodes are forced to speak with one voice, or nothing can be said
at all.

Thanks again for your reply, what do you think?

Camille.

> But it sounds like some of your ideas may mitigate this issue.
>
> Sent from my iPhone
>
>> On Aug 21, 2017, at 4:06 PM, Camille Harang via cryptography <cryptography at metzdowd.com> wrote:
>>
>> 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.
>>
>> _______________________________________________
>> The cryptography mailing list
>> cryptography at metzdowd.com
>> http://www.metzdowd.com/mailman/listinfo/cryptography