Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 2E20471F for ; Tue, 7 Feb 2017 11:27:59 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from BAY004-OMC2S25.hotmail.com (bay004-omc2s25.hotmail.com [65.54.190.100]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DB713AF for ; Tue, 7 Feb 2017 11:27:57 +0000 (UTC) Received: from NAM02-SN1-obe.outbound.protection.outlook.com ([65.54.190.125]) by BAY004-OMC2S25.hotmail.com over TLS secured channel with Microsoft SMTPSVC(7.5.7601.23008); Tue, 7 Feb 2017 03:27:57 -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=m82t399v+K3tUIrZr8kHhXpxSNqen1bd8mlznGQkpCg=; b=keRN4q9j0VWPH+YkFmy9K554pS7pC3FCV3w3ikIen7jUwEnMk8meNObcrRpU1py4sLyav4xO3hqKFqF3YEJoQ+WstQhCZ4eBKErypFvFMrIvxyWWdAv1PIPp7vd35jNCZZC+SVshx9TkmCo8EAUxpCS1pU4qb/hmCchONnK1RWHlWTo98JlfjkNRpjsRhfu0VygrWWyjorCnDtwQWT7lC0/bwYgkAmQ3i7syo3jimpGqVXsHBCYFHn819VuNJ81FtcjI9l2xL4VIv+3ctZcekcRx7SjQpEt+n9U3oEMCU7its+RORIeGro8eYE/f1gtYV5O/QTTEMd3OdpD092tjKg== Received: from CY1NAM02FT040.eop-nam02.prod.protection.outlook.com (10.152.74.59) by CY1NAM02HT052.eop-nam02.prod.protection.outlook.com (10.152.75.14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.888.7; Tue, 7 Feb 2017 11:27:56 +0000 Received: from BL2PR03MB435.namprd03.prod.outlook.com (10.152.74.51) by CY1NAM02FT040.mail.protection.outlook.com (10.152.75.135) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.888.7 via Frontend Transport; Tue, 7 Feb 2017 11:27:56 +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.026; Tue, 7 Feb 2017 11:27:56 +0000 From: John Hardy To: "bitcoin-dev@lists.linuxfoundation.org" Thread-Topic: Proof of Nodework (PoNW) - a method to trustlessly reward nodes for storing and verifying the blockchain Thread-Index: AQHSgTURNQj70TZ4G063Cioon3OvHg== Sender: John Hardy Date: Tue, 7 Feb 2017 11:27:55 +0000 Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: lists.linuxfoundation.org; dkim=none (message not signed) header.d=none; lists.linuxfoundation.org; dmarc=none action=none header.from=seebitcoin.com; x-incomingtopheadermarker: OriginalChecksum:1485453DCF081D6A6610A130A0F4173BB6B13CDA67EE16E28B33D4BE204597BC; UpperCasedChecksum:EBD21A21971863B4BB44F2DD8E03F8771FCEF1EAA8E77727F282CB0DC9F28698; SizeAsReceived:7819; Count:38 x-ms-exchange-messagesentrepresentingtype: 2 x-tmn: [mjIPmeB0UdjrF3vSqxJcL+32CilxfVk5] x-incomingheadercount: 38 x-eopattributedmessage: 0 x-microsoft-exchange-diagnostics: 1; CY1NAM02HT052; 5:GdxSoR0k9XhiUmORDFipZnEevyT1TcacCp06NPRjLSzK+IucpWSiNjwBKXsiUi2c5dAyOWIDH6Wpd13cLf03z0ns9nuupbRDND5HdmhpMKzIxNkCllwDGF1lWBA4uSLkZ691akI3LYezxsLd9D1hM18hD0Ack4zwBOEoRgQhy/Y=; 24:j/6UaZ+ecx4xrq49iOUoAD2dob7pTSxwTPi/+g2M7QXiYOEKAWGq0EnuS2VtPSCbicYAtlRiUuBkLsSDoAYe33QwEmu+dHV40hULAhoG7a4=; 7:0/GmOb/63kqF78jer6Je/hpoe6bGBdMYOmDDQAUJMbzrJT+hNsZT/IMDRMv021dLf0Mxb1fTKZwM/6TYdbntjcBgjGK0VfZ5eZRpV3aelYXBIV90qxr2tf0JOXpw+6HgLEKO4o3TL+FFF794YyzfkJr2bOmTcHyF9I/5ZFjw6bf7pLlu8VNWv+fYqc+aXHfKsfTFaeGCfTGxMIzmXeuQsQe414SwrQcaK3iS39ONPvdChwP68VJPYcXKe1aLSHXvDksmqQ59EmVWDG7n+tVPf3d42v72iMwRyM9J5NRPgXThmLGz4xgr9yslIHf75TzESIUFDcP+XO8F/4HknpzzpfIdtyQKYIU6U1+S1CrrrCCdBrQ2YbD8VlbZK6yCe0Pjg+zi10KW0rKO0KeKbrukJp6kCQmbcXQ6f1IobtMcytF3ib/B2Fd5arM6I8zxLbs86vixIbQFgIhZ57gAydhuMlVmGcWPPuOpL10F/yOMCZsfmxh/dijKu5WoSYjfFwaYRSSqE21JFPtr+TzeAqNxWw== x-forefront-antispam-report: EFV:NLI; SFV:NSPM; SFS:(10019020)(98900005); DIR:OUT; SFP:1102; SCL:1; SRVR:CY1NAM02HT052; H:BL2PR03MB435.namprd03.prod.outlook.com; FPR:; SPF:None; LANG:en; x-ms-office365-filtering-correlation-id: effea33a-cd82-48c7-c538-08d44f4c5d14 x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(5061506426)(5061507331)(1603103135)(1603101373)(1601125107)(1701031045); SRVR:CY1NAM02HT052; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(444111334)(432015086)(82015046); SRVR:CY1NAM02HT052; BCL:0; PCL:0; RULEID:; SRVR:CY1NAM02HT052; x-forefront-prvs: 0211965D06 spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: multipart/alternative; boundary="_000_BL2PR03MB435AA04A0AB8AC0E7781CA7EE430BL2PR03MB435namprd_" MIME-Version: 1.0 X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Feb 2017 11:27:55.8659 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY1NAM02HT052 X-OriginalArrivalTime: 07 Feb 2017 11:27:57.0595 (UTC) FILETIME=[3B56A6B0:01D28135] X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,HTML_MESSAGE, RCVD_IN_DNSWL_LOW 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: Fri, 10 Feb 2017 10:23:41 +0000 Subject: [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: Tue, 07 Feb 2017 11:27:59 -0000 --_000_BL2PR03MB435AA04A0AB8AC0E7781CA7EE430BL2PR03MB435namprd_ Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable 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 --_000_BL2PR03MB435AA04A0AB8AC0E7781CA7EE430BL2PR03MB435namprd_ Content-Type: text/html; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable

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


Hopefully they a= lso do 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 requi= re a new separate 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 prev= ent 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 stored in the nodeblock. Once a node can see that its addNode transaction has been added it can begin th= e PoNW process. The node=92s registered address will be hashed with the blo= ck header of the block it wants to work on. This will determine exactly whe= re 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=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 o= f 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, 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 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 nodeWorkCom= plete transaction 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 prev= ent nodes 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= 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 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 spe= cial new tx donation fee for nodes. If there was some way for users to =91d= onate=92 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 relati= vely effective way to create a reward for all nodes participating on a network. I=92d be keen to field any quest= ions or critiques.


Thanks,


John Hardy

john@seebitcoin.com

--_000_BL2PR03MB435AA04A0AB8AC0E7781CA7EE430BL2PR03MB435namprd_--