Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WYIoA-0008QC-U3 for bitcoin-development@lists.sourceforge.net; Thu, 10 Apr 2014 17:30:38 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.216.179 as permitted sender) client-ip=209.85.216.179; envelope-from=tier.nolan@gmail.com; helo=mail-qc0-f179.google.com; Received: from mail-qc0-f179.google.com ([209.85.216.179]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1WYIo9-00009X-Py for bitcoin-development@lists.sourceforge.net; Thu, 10 Apr 2014 17:30:38 +0000 Received: by mail-qc0-f179.google.com with SMTP id m20so4813770qcx.10 for ; Thu, 10 Apr 2014 10:30:32 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.229.112.5 with SMTP id u5mr22485464qcp.3.1397151032305; Thu, 10 Apr 2014 10:30:32 -0700 (PDT) Received: by 10.140.25.86 with HTTP; Thu, 10 Apr 2014 10:30:32 -0700 (PDT) In-Reply-To: References: <534570A2.9090502@gmx.de> <0B038624-8861-438E-B7B1-566B4A8E126B@bitsofproof.com> Date: Thu, 10 Apr 2014 18:30:32 +0100 Message-ID: From: Tier Nolan To: Bitcoin Dev Content-Type: multipart/alternative; boundary=001a11330a74fa720f04f6b3920c X-Spam-Score: -0.6 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (tier.nolan[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1WYIo9-00009X-Py Subject: Re: [Bitcoin-development] Bitcoind-in-background mode for SPV wallets X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Apr 2014 17:30:39 -0000 --001a11330a74fa720f04f6b3920c Content-Type: text/plain; charset=ISO-8859-1 Error correction is an interesting suggestion. If there was 10000 nodes and each stored 0.1% of the blocks, at random, then the odds of a block not being stored is 45 in a million. Blocks are stored on average 10 times, so there is already reasonable redundancy. With 1 million blocks, 45 would be lost in that case, even though most are stored multiple times. With error correction codes, the chances of blocks going missing is much lower. For example, if there was 32 out of 34 Reed-Solomon-like system, then 2 blocks out of 34 could be lost without any actual data loss for the network. As a back of the envelop check, the odds of 2 missing blocks landing within 34 of another is 68/1000000. That means that the odds of 2 missing blocks falling in the same correction section is 45 * 34 / 1000000 = 0.153%. Even in that case, the missing blocks could be reconstructed, as long as you know that they are missing. The error correction code has taken it from being a near certainty that some blocks would be lost to less than 0.153%. A simple error correction system would just take 32 blocks in sequence and then compute 2 extra blocks. The extra blocks would have to be the same length as the longest block in the 32 being corrected. The shorter blocks would be padded with zeroes so everything is the same size. For each byte position in the blocks you compute the polynomial that goes through byte (x, data(x)), for x = 0 to 31. This could be a finite field, or just mod 257. You can then compute the value for x=32 and x = 33. Those are the values for the 2 extra blocks. If mod 257 is used, then only the 2 extra blocks have to deal with symbols from 0 to 256. If you have 32 of the 34 blocks, you can compute the polynomial and thus generate the 32 actual blocks. This could be achieved by a soft fork by having a commitment every 32 blocks in the coinbase. It makes the header chain much longer though. Longer sections are more efficient, but need more calculations to recover everything. You could also do interleaving to handle the case where entire sections are missing. On Thu, Apr 10, 2014 at 12:54 PM, Peter Todd wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA512 > > > > On 10 April 2014 07:50:55 GMT-04:00, Gregory Maxwell > wrote: > >(Just be glad I'm not suggesting coding the entire blockchain with an > >error correcting code so that it doesn't matter which subset you're > >holding) > > I forgot to ask last night: if you do that, can you add new blocks to the > chain with the encoding incrementally? > -----BEGIN PGP SIGNATURE----- > Version: APG v1.1.1 > > iQFQBAEBCgA6BQJTRoZ+MxxQZXRlciBUb2RkIChsb3cgc2VjdXJpdHkga2V5KSA8 > cGV0ZUBwZXRlcnRvZGQub3JnPgAKCRAZnIM7qOfwhYudCAC7ImifMnLIFHv1UifV > zRxtDkx7UxIf9dncDAcrTIyKEDhoouh0TmoZl3HKQ3KUEETAVKsMzqXLgqVe6Ezr > ny1bm0pQlkBCZFRwuZvmB27Y3mwC8PD6rT9ywtWzFjWd8PEg6/UaM547nQPw7ir0 > 27S3XMfE/BMiQWfWnWc/nqpbmJjd8x/dM3oiTG9SVZ7iNxotxAqfnW2X5tkhJb0q > dAV08wpu6aZ5hTyLpvDxXDFjEG119HJeLkT9QVIrg+GBG55PYORqE4gQr6uhrF4L > fGZS2EIlbk+kAiv0EjglQfxWM7KSRegplSASiKEOuX80tqLIsEugNh1em8qvG401 > NOAS > =CWql > -----END PGP SIGNATURE----- > > > > ------------------------------------------------------------------------------ > Put Bad Developers to Shame > Dominate Development with Jenkins Continuous Integration > Continuously Automate Build, Test & Deployment > Start a new project now. Try Jenkins in the cloud. > http://p.sf.net/sfu/13600_Cloudbees > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > --001a11330a74fa720f04f6b3920c Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Error correction is an interesting suggestion.
If there was 10000 nodes and each stored 0.1% of the blocks, at= random, then the odds of a block not being stored is 45 in a million.

Blocks are stored on average 10 times, so there is already r= easonable redundancy.

With 1 million blocks, 4= 5 would be lost in that case, even though most are stored multiple times.
With error correction codes, the chances of blocks going mis= sing is much lower.

For example, if there was 32 out of 3= 4 Reed-Solomon-like system, then 2 blocks out of 34 could be lost without a= ny actual data loss for the network.

As a back of the envelop check, the odds of 2 missing blocks= landing within 34 of another is 68/1000000.=A0 That means that the odds of= 2 missing blocks falling in the same correction section is 45 * 34 / 10000= 00 =3D 0.153%.=A0 Even in that case, the missing blocks could be reconstruc= ted, as long as you know that they are missing.

The error correction code has taken it from being a near cer= tainty that some blocks would be lost to less than 0.153%.

A simple error correction system would just take 32 blocks in sequence an= d then compute 2 extra blocks.

The extra blocks would have to be the same length as the lon= gest block in the 32 being corrected.

The shorter blocks = would be padded with zeroes so everything is the same size.

For each= byte position in the blocks you compute the polynomial that goes through b= yte (x, data(x)), for x =3D 0 to 31.=A0 This could be a finite field, or ju= st mod 257.

You can then compute the value for x=3D32 and x =3D 33.=A0 T= hose are the values for the 2 extra blocks.

If mod 257 is= used, then only the 2 extra blocks have to deal with symbols from 0 to 256= .

If you have 32 of the 34 blocks, you can compute the polynom= ial and thus generate the 32 actual blocks.

This could be= achieved by a soft fork by having a commitment every 32 blocks in the coin= base.

It makes the header chain much longer though.

<= div>Longer sections are more efficient, but need more calculations to recov= er everything.=A0 You could also do interleaving to handle the case where e= ntire sections are missing.


O= n Thu, Apr 10, 2014 at 12:54 PM, Peter Todd <pete@petertodd.org>= wrote:
-----BEGIN PGP SIGNED MESSAG= E-----
Hash: SHA512



On 10 April 2014 07:50:55 GMT-04:00, Gregory Maxwell = <gmaxwell@gmail.com> wrote:=
>(Just be glad I'm not suggesting coding the entire blockchain with = an
>error correcting code so that it doesn't matter which subset you= 9;re
>holding)

I forgot to ask last night: if you do that, can you add new blocks to= the chain with the encoding incrementally?
-----BEGIN PGP SIGNATURE-----
Version: APG v1.1.1

iQFQBAEBCgA6BQJTRoZ+MxxQZXRlciBUb2RkIChsb3cgc2VjdXJpdHkga2V5KSA8
cGV0ZUBwZXRlcnRvZGQub3JnPgAKCRAZnIM7qOfwhYudCAC7ImifMnLIFHv1UifV
zRxtDkx7UxIf9dncDAcrTIyKEDhoouh0TmoZl3HKQ3KUEETAVKsMzqXLgqVe6Ezr
ny1bm0pQlkBCZFRwuZvmB27Y3mwC8PD6rT9ywtWzFjWd8PEg6/UaM547nQPw7ir0
27S3XMfE/BMiQWfWnWc/nqpbmJjd8x/dM3oiTG9SVZ7iNxotxAqfnW2X5tkhJb0q
dAV08wpu6aZ5hTyLpvDxXDFjEG119HJeLkT9QVIrg+GBG55PYORqE4gQr6uhrF4L
fGZS2EIlbk+kAiv0EjglQfxWM7KSRegplSASiKEOuX80tqLIsEugNh1em8qvG401
NOAS
=3DCWql
-----END PGP SIGNATURE-----


---------------------------------------------------------------------------= ---
Put Bad Developers to Shame
Dominate Development with Jenkins Continuous Integration
Continuously Automate Build, Test & Deployment
Start a new project now. Try Jenkins in the cloud.
http://p.= sf.net/sfu/13600_Cloudbees
_______________________________________________
Bitcoin-development mailing list
Bitcoin-develo= pment@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment

--001a11330a74fa720f04f6b3920c--