Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 86AAA978 for ; Mon, 13 Feb 2017 11:58:12 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from BAY004-OMC3S27.hotmail.com (bay004-omc3s27.hotmail.com [65.54.190.165]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4967D106 for ; Mon, 13 Feb 2017 11:58:11 +0000 (UTC) Received: from NAM01-SN1-obe.outbound.protection.outlook.com ([65.54.190.187]) by BAY004-OMC3S27.hotmail.com over TLS secured channel with Microsoft SMTPSVC(7.5.7601.23008); Mon, 13 Feb 2017 03:58:10 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=iXWsOI1eCvfAD6BGHmAw3gqamMLh5mQnRQn0VY2UHMs=; b=K8MLgSGc2Va2+P8f+Xl3y48yPdNacAtjbgc92k1CtyjOJfbs4fEXC7lVy3dJsdtD6TEPc/uqBIcM7kSsOQMwQ/7n6AU5iv8EyCvA8uxXlsPLu+8gQVQsQgC2jAdCRoBe4TPz/vPI0QRAszaDkvSOTULZEJkoNAAOkkWmQmYXtklWqh7XMecxGMiglZA99HO5e5OyhJUCcHRKGw6J3hUGIp1DOevMPEAqpcAHMHZuuZkF23OrOyAIRYGQu5adWaxCbCBNcm2ySmLO4Pq3JLtWvYFWkM9TCNFqNDwECD5vdwFy7k7kL74Rk350Af0Jnpvp+i7azO0Dc7Mes6N6kJNpfg== Received: from SN1NAM01FT043.eop-nam01.prod.protection.outlook.com (10.152.64.51) by SN1NAM01HT132.eop-nam01.prod.protection.outlook.com (10.152.64.139) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.904.16; Mon, 13 Feb 2017 11:58:09 +0000 Received: from BL2PR03MB435.namprd03.prod.outlook.com (10.152.64.56) by SN1NAM01FT043.mail.protection.outlook.com (10.152.65.216) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.904.16 via Frontend Transport; Mon, 13 Feb 2017 11:58:09 +0000 Received: from BL2PR03MB435.namprd03.prod.outlook.com ([10.141.92.24]) by BL2PR03MB435.namprd03.prod.outlook.com ([10.141.92.24]) with mapi id 15.01.0888.030; Mon, 13 Feb 2017 11:58:09 +0000 From: John Hardy To: Sergio Demian Lerner , "bitcoin-dev@lists.linuxfoundation.org" Thread-Topic: [bitcoin-dev] Proof of Nodework (PoNW) - a method to trustlessly reward nodes for storing and verifying the blockchain Thread-Index: AQHSgTURNQj70TZ4G063Cioon3OvHqFl2RGAgAD29N4= Sender: John Hardy Date: Mon, 13 Feb 2017 11:58:09 +0000 Message-ID: References: , In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: gmail.com; dkim=none (message not signed) header.d=none; gmail.com; dmarc=none action=none header.from=seebitcoin.com; x-incomingtopheadermarker: OriginalChecksum:903F6F2B3EFE7CA2F158F80ADC47079D07B9ED7C7B8AD94E558F045249B9880E; UpperCasedChecksum:331DC7CBE29F0658A91421ED5DAA2B6C09CD320F8A0C2E1EE91B34F2CE866B9B; SizeAsReceived:8161; Count:40 x-ms-exchange-messagesentrepresentingtype: 2 x-tmn: [ek8mYwUxYznHmWiM+3toW14tEXWiVeKG] x-incomingheadercount: 40 x-eopattributedmessage: 0 x-microsoft-exchange-diagnostics: 1; SN1NAM01HT132; 5:4KqFYHvHjZRxtFCHN1419WpeB9NjKggWsxKun7fSxHYc+/EcQK0qjN31P+Z+KOxCxspAsDcf4fFMhJ7Vv3yVQwMVTHgn16Wn4RU0WqS9dzxz7agxNweuzkoLi9j6mNHG1gdDiEw6XGyVd9AB5cSNzA==; 24:3QF9SrhQMqvhARf8YDI3ZFvGCLN0tPhaspX1YPelKW4z7XfBZ+tO7ECTTFT0y7tQNRqC8lD5Pjkw43CI9yoAyleI55EiZa+/6Qy75uSc3F4=; 7:Uy6MRs+/uPXklJgJ0O+NDYO4Ar9onCJ5KS30+GcXCD5zNUVVCI8b4f9pittdJUD8dy1xHhsHCHR8HViuVeAXJWOwfQh3khpQeo1ZfmhH3CstGGjjQpnOmBLXHlnp7nIyme4wXF1qnoipkZzO2fcuYXQhu7pfA2MbvGHepmxv32/e6dh5cITHxUu+v15gfLmnljIypBNdg3p32Zz1bdXmd7U+anzlzvZ7JNbakaexiPNDGpGy7XpzJBeH7zmU+Cq5AYb4sBq/wFNIpGF3udA4+dYtOfibHAPPf0gOeC5yWoSysMys+12ll18osjJVRWpL84PRDFtxchZrCsEZho8IXrXOqbdJQw6WT+zQij9ecQhbuuThY5FWR3bT5SAiyoI5Dw7aI2CoQ5BQeFxgXjEQw99415lkEC5Ufb3CPa3WQ74Vuy3xqWt5g6sPX6x03lxT/tFSeK/TKyagpalv9OAEKeWLhEuhRNtw35CKjKEJJzbfvBaXvlvThXXcb05EyyMgxPhEMV2UVrCgaAlC/PDukg== x-forefront-antispam-report: EFV:NLI; SFV:NSPM; SFS:(10019020)(98900007); DIR:OUT; SFP:1102; SCL:1; SRVR:SN1NAM01HT132; H:BL2PR03MB435.namprd03.prod.outlook.com; FPR:; SPF:None; LANG:en; x-ms-office365-filtering-correlation-id: 5b50f778-e42e-4285-116e-08d454079465 x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(5061506426)(5061507331)(1603103135)(1603101373)(1601125107)(1701031045); SRVR:SN1NAM01HT132; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(432015086)(82015046); SRVR:SN1NAM01HT132; BCL:0; PCL:0; RULEID:; SRVR:SN1NAM01HT132; x-forefront-prvs: 02176E2458 spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: multipart/alternative; boundary="_000_BL2PR03MB4355F39BE003DBF200591EBEE590BL2PR03MB435namprd_" MIME-Version: 1.0 X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-originalarrivaltime: 13 Feb 2017 11:58:09.1373 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN1NAM01HT132 X-OriginalArrivalTime: 13 Feb 2017 11:58:10.0797 (UTC) FILETIME=[7291D1D0:01D285F0] X-Spam-Status: No, score=-1.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=no 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 12:07:38 +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: Mon, 13 Feb 2017 11:58:12 -0000 --_000_BL2PR03MB4355F39BE003DBF200591EBEE590BL2PR03MB435namprd_ Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable Hi Sergio, Thanks for your response, interesting work, very excited for RSK. I like the ephemeral payload, I suppose that aspect of my proposal could be= described as ephemeral blockspace. I'm curious about the challenge phase, what incentive do nodes to have to c= heck other nodes' responses? Is any validation of responses mandatory, or d= oes policing the system rely on altruism? I also wondered how time-based responses are enforced? What prevents a mine= r censoring challenge responses so they do not get included in a block 'in = time' - if inclusion within a block is the mechanism used? I saw your tweet on Lumino - sounds very promising. Would be keen to take a= look at the paper if you're looking for any additional review at this stag= e. Regards, John Hardy ________________________________ From: Sergio Demian Lerner Sent: Sunday, February 12, 2017 8:22 PM To: John Hardy; Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Proof of Nodework (PoNW) - a method to trustless= ly reward nodes for storing and verifying the blockchain Hi John, RSK platform (a Bitcoin sidechain) is already prepared to do something sim= ilar to this, although very efficiently. We set apart 1% of the block rewar= d 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, bu= t 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 o= f 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 transactio= n 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 (o= nly the ones created by misbehaving users). Because RSK/Rootstock has a very short block interval (10 seconds), all thi= s 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 > 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 =91traditional=92 node activities too like re= lay transactions and blocks, but there isn=92t really any way I can think o= f to trustlessly verify this also. PoNW would require a new separate area of block space, a nodeblock, purely = concerned with administering the system. A nodeblock is committed to a bloc= k as with SegWit. A recent history of nodeblocks needs to be stored by node= s, 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 submi= tting an addNode transaction - along with a security deposit to prevent che= ating. This transaction will be stored in the nodeblock. Once a node can see that = its addNode transaction has been added it can begin the PoNW process. The n= ode=92s registered address will be hashed with the block header of the bloc= k it wants to work on. This will determine exactly where within the blockch= ain to begin the PoNW. The PoNW method could be as simple as creating a Merkle tree from the rando= mly generated point on the blockchain, though a method that is CPU/Memory h= eavy and less likely to be replaced by dedicated hardware like ASICs would = be better. This process could not begin until the most recent block has bee= n fully verified, and while being carried out should still enable normal re= lay activities to proceed as normal, since it shouldn=92t tie up network at= all. The data processed should also be mixed with data from the latest blo= ck 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 t= hen create a nodeWorkComplete transaction for that block with its final pro= of value, add how much =91work=92 it did - and create a couple of assertion= s about what it processed (such as there were x number of pieces of data ma= tching a particular value during calculating). These assertions can be accu= rate or inaccurate. The system will run in epochs. 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 from a node=92s address and blockhash will also b= e 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 nod= e to verify - and this will randomly be a large number of smaller PoNW tran= sactions, or a smaller number of large PoNW. This process will be determini= stic based on that block and address hash. All the data will be put togethe= r in a transaction and then signed by the node addresses private key. If a nodeWorkComplete transaction contains any incorrect information in an = attempt to cheat the validation process a challenge transaction can be crea= ted. 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 securit= y deposit. Nodes will also be punished if they broadcast more than one signed transact= ion per block. In order to prevent nodes from having multiple keys registered - which woul= d enable them choose to perform PoNW on a subset of the data that they hold= - the share of reward that the node gets will be multiplied based on the n= umber of blocks within an epoch that the node performs PoNW on. The share o= f reward is limited based on how much security deposit has been staked. The= higher the PoNW the higher the deposit needed in order to claim their full= allocation of any reward. At the end of an epoch, with a wait period for any delayed or censored tran= sactions or challenges to be included and settled up, the process of calcul= ating 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 per= manent 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 block without correctly calculating and paying the due reward wil= l 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 donatio= n fee for nodes. If there was some way for users to =91donate=92 to the rew= ard pool for nodes this would increase the incentive for additional nodes t= o participate on the network in the event of centralisation. This is a relatively effective way to create a reward for all nodes partici= pating on a network. I=92d 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 --_000_BL2PR03MB4355F39BE003DBF200591EBEE590BL2PR03MB435namprd_ Content-Type: text/html; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable

Hi Sergio,


Thanks for your response, interesting work, very excited for RSK.


I like the ephemeral payload, I suppose that aspect of my proposal could= be described as ephemeral blockspace.


I'm curious about the challenge phase, what incentive do nodes to have t= o check other nodes' responses? Is any validation of responses mandatory, o= r does policing the system rely on altruism?


I also wondered how time-based responses are enforced? What prevents a m= iner censoring challenge responses so they do not get included in a block '= in time' - if  inclusion within a block is the mechanism used?


I saw your tweet on Lumino - sounds very promising. Would be keen to tak= e a look at the paper if you're looking for any additional review at this s= tage.


Regards,


John Hardy



From: Sergio Demian Lerner = <sergio.d.lerner@gmail.com>
Sent: Sunday, February 12, 2017 8:22 PM
To: John Hardy; Bitcoin Protocol Discussion
Subject: Re: [bitcoin-dev] Proof of Nodework (PoNW) - a method to tr= ustlessly reward nodes for storing and verifying the blockchain
 
Hi John,
 RSK platform (a Bitcoin sidechain) is already prepared to do som= ething similar to this, although very efficiently. We set apart 1% of the b= lock reward to automatically reward full nodes.

We have two systems being evaluated: the first is based on PoUBS (Proo= f of Unique Blockchain Storage) which uses asymmetric-time operations to en= code the blockchain based on each user public key such that decoding is fas= t, but encoding is slow. The second is more traditional proof of retrievability, but it requires some ASIC-res= istance assumptions. 

In both cases, a special smart contract is being called at every block= that creates periodic challenges. Every full node that wants to participat= e can submits a commitment to the Merkle hash root of a pseudo-random seque= nce of encoded blocks. Then the smart contract chooses random elements from the committed dataset, and eac= h 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 transa= ction payload: Ephemeral Payload. Ephemeral payload is a payload in a trans= action that gets discarded after N blocks if no smart contract does referen= ce 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 s= mart contract ONLY evaluates the responses which have been questioned by us= ers.

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

Because RSK/Rootstock has a very short block interval (10 seconds), al= l 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 b= itcoin-dev <bitcoin-dev@lists.linuxfoundation.org> = wrote:

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


Hopefully they also d= o useful =91traditional=92 node activities too like relay transactions and blocks, but there isn=92t really any way I= can think of to trustlessly verify this also.


PoNW would require a = new separate area of block space, a nodeblock, purely concerned with administering the system. A nodeblock is committed t= o 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 nee= d to be retained forever.


In order to prevent S= ybil, 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 stored in the nodeblock. Once a node can see that its addNode transaction has been added it can begin the PoNW = process. The node=92s registered address will be hashed with the block head= er of the block it wants to work on. This will determine exactly where with= in 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 li= ke ASICs would be better. This process could not begin until the most recen= t block has been fully verified, and while being carried out should still enable normal relay activities to= proceed as normal, since it shouldn=92t tie up network at all. The data pr= ocessed should also be mixed with data from the latest block so that it can= not 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 =91work=92 it did - and create a couple 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 i= n epochs. 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 gener= ated from a node=92s 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= transaction contains any incorrect information in an attempt to cheat the validation process a challenge transaction can = be created. This begins a refereeing process where other nodes check the ch= allenge and vote whether it is to be upheld or not. The losing node is puni= shed by losing their accrued PoNW for that epoch and a percentage of their security deposit.


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


In order to prevent n= odes from 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 epoc= h, 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 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 how much the reward comes from is a different one. It could come from the existing miner reward, or a specia= l new tx donation fee for nodes. If there was some way for users to =91dona= te=92 to the reward pool for nodes this would increase the incentive for ad= ditional 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=92d 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


--_000_BL2PR03MB4355F39BE003DBF200591EBEE590BL2PR03MB435namprd_--