Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 5693D6C for ; Sun, 12 Feb 2017 20:23:16 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-qk0-f169.google.com (mail-qk0-f169.google.com [209.85.220.169]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DD88314C for ; Sun, 12 Feb 2017 20:23:14 +0000 (UTC) Received: by mail-qk0-f169.google.com with SMTP id u25so78798862qki.2 for ; Sun, 12 Feb 2017 12:23:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=gtsAvBGpmS1T7VEMpJxxLislGlrbmsF3h/rusas458U=; b=dpNqiaepnphXEbouTyMW8Ypb8OYiU5kGHfN+1csFBzBPLT1AZzRyBm/oCCe+f5bDzq yVaQfxeeiJ25Sl3MWKq0moIruR9cAMetvFFjTTfx/y37Jujd6HWSpkrIKerk5xydGUIh AU5QelmhIu2LO6KK4DW6ArqNk7TCe+HF6MI6BvHa9i66wero25WsB184ZTacakQGhD8S NMQPR1BnphFWq4xVXgnaX6sDEl6NqaWqE3q8ByniJY3WPfmDDnteK+F8PmZDymP/4+A2 wF3crw+dYsqLiUR0qnfFK+uM8ZpoiQ/r//Rm7LMIr5LZ1OQuXmQMvuAje6jccTLhaOf0 5o+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=gtsAvBGpmS1T7VEMpJxxLislGlrbmsF3h/rusas458U=; b=Zqz7E15muHs2xCJmHymQJNB/Nj6DMnNjhjUB8XIb2Y+LXHXv00R8ku2wDQxPVssACu JyL1DXxCETxd2JbFsMdtTM1/6gtGcYtjTktRryRpUe2Tx9tY6XVDiQaVc6Bs+O0lZhat aaRiPu+csizn0HikIFFOai1ntnwXQ85lRasBtPg1cfQHicNovIkOtPr3sWQDCjmHXj/N RgR/XkMAEFyyGkw0wqfxotESC68v1vh0UVlUUAeAD/naY9tAjI3ID0i+Cs1Rw7yCD+UG ZqD5VfCSNVq0MY/KYhWJ/rd8E+RHLtlk0iggJNTby5s/cGdcz9YaBrsN3nu81AfxNXwG MP1w== X-Gm-Message-State: AMke39lgRliCpsTGYAAzXG4zxoT6hOv2nQPATUolYDP+nLi+MMqC7ihxlHaPd7yGkaoXl3bW95rszMO28LCaVA== X-Received: by 10.55.204.92 with SMTP id r89mr3611345qki.306.1486930993993; Sun, 12 Feb 2017 12:23:13 -0800 (PST) MIME-Version: 1.0 Received: by 10.237.52.1 with HTTP; Sun, 12 Feb 2017 12:22:33 -0800 (PST) In-Reply-To: References: From: Sergio Demian Lerner Date: Sun, 12 Feb 2017 17:22:33 -0300 Message-ID: To: John Hardy , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=001a1149adeeb3dfe805485b19ff X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Mon, 13 Feb 2017 07:57:57 +0000 Subject: Re: [bitcoin-dev] Proof of Nodework (PoNW) - a method to trustlessly reward nodes for storing and verifying the blockchain X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 12 Feb 2017 20:23:16 -0000 --001a1149adeeb3dfe805485b19ff Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hi John, RSK platform (a Bitcoin sidechain) is already prepared to do something similar to this, although very efficiently. We set apart 1% of the block reward to automatically reward full nodes. We have two systems being evaluated: the first is based on PoUBS (Proof of Unique Blockchain Storage) which uses asymmetric-time operations to encode the blockchain based on each user public key such that decoding is fast, but encoding is slow. The second is more traditional proof of retrievability, but it requires some ASIC-resistance assumptions. In both cases, a special smart contract is being called at every block that creates periodic challenges. Every full node that wants to participate can submits a commitment to the Merkle hash root of a pseudo-random sequence of encoded blocks. Then the smart contract chooses random elements from the committed dataset, and each full node has a period to submit Merkle-proofs that such random elements belong to the commitment. To prevent blockchain bloat we designed a very cool new type of transaction payload: Ephemeral Payload. Ephemeral payload is a payload in a transaction that gets discarded after N blocks if no smart contract does reference it. If is does, it's solidified forever in the blockchain. Then there is a challenge phase where other full nodes can inform the smart contract if they find an error in the submitted responses. Then the smart contract ONLY evaluates the responses which have been questioned by users. This way the smart contract does very little computation (only when a user misbehaves) and the blockchain normally does not store any proof forever (only the ones created by misbehaving users). Because RSK/Rootstock has a very short block interval (10 seconds), all this happens very quickly and does not require much computation. Best regards, Sergio Lerner Chief Scientist RSK (aka Roostock) On Tue, Feb 7, 2017 at 8:27 AM, John Hardy via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Proof of Nodework (PoNW) is a way to reward individual nodes for keeping = a > full copy of and verifying the blockchain. > > Hopefully they also do useful =E2=80=98traditional=E2=80=99 node activiti= es too like relay > transactions and blocks, but there isn=E2=80=99t really any way I can thi= nk of to > trustlessly verify this also. > > PoNW would require a new separate area of block space, a nodeblock, purel= y > concerned with administering the system. A nodeblock is committed to a > block as with SegWit. A recent history of nodeblocks needs to be stored b= y > nodes, however the data eventually becomes obsolete and so does not need = to > be retained forever. > > In order to prevent Sybil, a node must register an Bitcoin address by > submitting an addNode transaction - along with a security deposit to > prevent cheating. > > This transaction will be stored in the nodeblock. Once a node can see tha= t > its addNode transaction has been added it can begin the PoNW process. The > node=E2=80=99s registered address will be hashed with the block header of= the block > it wants to work on. This will determine exactly where within the > blockchain to begin the PoNW. > > The PoNW method could be as simple as creating a Merkle tree from the > randomly generated point on the blockchain, though a method that is > CPU/Memory heavy and less likely to be replaced by dedicated hardware lik= e > ASICs would be better. This process could not begin until the most recent > block has been fully verified, and while being carried out should still > enable normal relay activities to proceed as normal, since it shouldn=E2= =80=99t tie > up network at all. The data processed should also be mixed with data from > the latest block so that it cannot be computed in advance. > > A node can do as much PoNW for a block as it likes. Once finished it will > then create a nodeWorkComplete transaction for that block with its final > proof value, add how much =E2=80=98work=E2=80=99 it did - and create a co= uple of assertions > about what it processed (such as there were x number of pieces of data > matching a particular value during calculating). These assertions can be > accurate or inaccurate. > > The system will run in epochs. During each epoch of say 2016 blocks, ther= e > will be an extended window for PoNW transactions to be added to nodeblock= s > to limit minor censorship. > > The random hash generated from a node=E2=80=99s address and blockhash wil= l also be > used to determine nodeWorkComplete transactions from a previous block tha= t > the node must also verify, and correctly calculate whether the assertions > it made were true or false. The average PoNW that a node performed in its > previous x nodeblocks will be used to determine the target PoNW for the > node to verify - and this will randomly be a large number of smaller PoNW > transactions, or a smaller number of large PoNW. This process will be > deterministic based on that block and address hash. All the data will be > put together in a transaction and then signed by the node addresses priva= te > key. > > If a nodeWorkComplete transaction contains any incorrect information in a= n > attempt to cheat the validation process a challenge transaction can be > created. This begins a refereeing process where other nodes check the > challenge and vote whether it is to be upheld or not. The losing node is > punished by losing their accrued PoNW for that epoch and a percentage of > their security deposit. > > Nodes will also be punished if they broadcast more than one signed > transaction per block. > > In order to prevent nodes from having multiple keys registered - which > would enable them choose to perform PoNW on a subset of the data that the= y > hold - the share of reward that the node gets will be multiplied based on > the number of blocks within an epoch that the node performs PoNW on. The > share of reward is limited based on how much security deposit has been > staked. The higher the PoNW the higher the deposit needed in order to cla= im > their full allocation of any reward. > > At the end of an epoch, with a wait period for any delayed or censored > transactions or challenges to be included and settled up, the process of > calculating the reward each node is due can begin. This will then be then > paid in a regular block, and means for all the data involved in PoNW, the > only permanent mark it makes on the main blockchain is for a transaction > that pays all addresses their share of the reward at the end of epoch. An= y > miner who creates a block without correctly calculating and paying the du= e > reward will have mined an invalid block and be orphaned. > > The question of where and how much the reward comes from is a different > one. It could come from the existing miner reward, or a special new tx > donation fee for nodes. If there was some way for users to =E2=80=98donat= e=E2=80=99 to the > reward pool for nodes this would increase the incentive for additional > nodes to participate on the network in the event of centralisation. > > This is a relatively effective way to create a reward for all nodes > participating on a network. I=E2=80=99d be keen to field any questions or= critiques. > > Thanks, > > > John Hardy > > john@seebitcoin.com > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a1149adeeb3dfe805485b19ff Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Hi John,
=C2=A0RSK platform (a Bitcoin sidechain) is a= lready prepared to do something similar to this, although very efficiently.= We set apart 1% of the block reward to automatically reward full nodes.

We have two systems being evaluated: the first is ba= sed on PoUBS (Proof of Unique Blockchain Storage) which uses asymmetric-tim= e operations to encode the blockchain based on each user public key such th= at decoding is fast, but encoding is slow. The second is more traditional p= roof of retrievability, but it requires some ASIC-resistance assumptions.= =C2=A0

In both cases, a special smart contract is = being called at every block that creates periodic challenges. Every full no= de that wants to participate can submits a commitment to the Merkle hash ro= ot of a pseudo-random sequence of encoded blocks. Then the smart contract c= hooses random elements from the committed dataset, and each full node has a= period to submit Merkle-proofs that such random elements belong to the com= mitment.

To prevent blockchain bloat we designed a= very cool new type of transaction payload: Ephemeral Payload. Ephemeral pa= yload is a payload in a transaction that gets discarded after N blocks if n= o smart contract does reference it. If is does, it's solidified forever= in the blockchain.
Then there is a challenge phase where other f= ull nodes can inform the smart contract if they find an error in the submit= ted responses. Then the smart contract ONLY evaluates the responses which h= ave been questioned by users.

This way the smart c= ontract does very little computation (only when a user misbehaves) and the = blockchain normally does not store any proof forever (only the ones created= by misbehaving users).

Because RSK/Rootstock has = a very short block interval (10 seconds), all this happens very quickly and= does not require much computation.=C2=A0

Best reg= ards,
=C2=A0Sergio Lerner
=C2=A0Chief Scientist RSK= (aka Roostock)


On Tue, Feb 7, 2017 at 8:27 AM, John Hardy via bit= coin-dev <bitcoin-dev@lists.linuxfoundation.org>= ; wrote:

= Proof of Nodework (PoNW) is= a way to reward individual nodes for keeping a full copy of and verifying the blockchain.


= Hopefully they also do usef= ul =E2=80=98traditional=E2=80=99 node activities too like relay transactions and blocks, but there isn=E2=80=99t really any= way I can think of to trustlessly verify this also.


= PoNW would require a new se= parate area of block space, a nodeblock, purely concerned with administering the system. A nodeblock i= s committed to a block as with SegWit. A recent history of nodeblocks needs= to be stored by nodes, however the data eventually becomes obsolete and so= does not need to be retained forever.


= In order to prevent Sybil, = a node must register an Bitcoin address by submitting an addNode transaction - along with a security depos= it to prevent cheating.


= This transaction will be st= ored in the nodeblock. Once a node can see that its addNode transaction has been added it can begin th= e PoNW process. The node=E2=80=99s registered address will be hashed with t= he block header of the block it wants to work on. This will determine exact= ly where within the blockchain to begin the PoNW.


= The PoNW method could be as= simple as creating a Merkle tree from the randomly generated point on the blockchain, though a method = that is CPU/Memory heavy and less likely to be replaced by dedicated hardwa= re like ASICs would be better. This process could not begin until the most = recent block has been fully verified, and while being carried out should still enable normal relay activities to= proceed as normal, since it shouldn=E2=80=99t tie up network at all. The d= ata processed should also be mixed with data from the latest block so that = it cannot be computed in advance.


= A node can do as much PoNW = for a block as it likes. Once finished it will then create a nodeWorkComplete transaction for that block= with its final proof value, add how much =E2=80=98work=E2=80=99 it did - a= nd create a couple of assertions about what it processed (such as there wer= e x number of pieces of data matching a particular value during calculating). These assertions can be accurate or inaccurate.=


= The system will run in epoc= hs. During each epoch of say 2016 blocks, there will be an extended window for PoNW transactions to be = added to nodeblocks to limit minor censorship.


= The random hash generated f= rom a node=E2=80=99s address and blockhash will also be used to determine nodeWorkComplete transactions from a previo= us block that the node must also verify, and correctly calculate whether th= e assertions it made were true or false. The average PoNW that a node perfo= rmed in its previous x nodeblocks will be used to determine the target PoNW for the node to verify - and thi= s will randomly be a large number of smaller PoNW transactions, or a smalle= r number of large PoNW. This process will be deterministic based on that bl= ock and address hash. All the data will be put together in a transaction and then signed by the node addresse= s private key.


= If a nodeWorkComplete trans= action contains any incorrect information in an attempt to cheat the validation process a challenge tran= saction can be created. This begins a refereeing process where other nodes = check the challenge and vote whether it is to be upheld or not. The losing = node is punished by losing their accrued PoNW for that epoch and a percentage of their security deposit.


= Nodes will also be punished= if they broadcast more than one signed transaction per block.


= In order to prevent nodes f= rom having multiple keys registered - which would enable them choose to perform PoNW on a subset of the data t= hat they hold - the share of reward that the node gets will be multiplied b= ased on the number of blocks within an epoch that the node performs PoNW on= . The share of reward is limited based on how much security deposit has been staked. The higher the PoNW th= e higher the deposit needed in order to claim their full allocation of any = reward.


= At the end of an epoch, wit= h a wait period for any delayed or censored transactions or challenges to be included and settled up, the = process of calculating the reward each node is due can begin. This will the= n be then paid in a regular block, and means for all the data involved in P= oNW, the only permanent mark it makes on the main blockchain is for a transaction that pays all addresses = their share of the reward at the end of epoch. Any miner who creates a bloc= k without correctly calculating and paying the due reward will have mined a= n invalid block and be orphaned.


= The question of where and h= ow much the reward comes from is a different one. It could come from the existing miner reward, or a spe= cial new tx donation fee for nodes. If there was some way for users to =E2= =80=98donate=E2=80=99 to the reward pool for nodes this would increase the = incentive for additional nodes to participate on the network in the event of centralisation.


= This is a relatively effect= ive way to create a reward for all nodes participating on a network. I=E2=80=99d be keen to field any= questions or critiques.


Thanks,


John Hardy

john@seebitcoin= .com


_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


--001a1149adeeb3dfe805485b19ff--