From: Tier Nolan <tier.nolan@gmail•com>
To: Bitcoin Dev <bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Bitcoind-in-background mode for SPV wallets
Date: Thu, 10 Apr 2014 18:30:32 +0100 [thread overview]
Message-ID: <CAE-z3OV4w+vQ0b6h9E+7cSyxkKENduyfHenhdF3q3-0i2chnGQ@mail.gmail.com> (raw)
In-Reply-To: <c3726067-5a9f-45b9-b798-1070bdde2ac4@email.android.com>
[-- Attachment #1: Type: text/plain, Size: 3682 bytes --]
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 <pete@petertodd•org> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> 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'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
>
[-- Attachment #2: Type: text/html, Size: 4812 bytes --]
next prev parent reply other threads:[~2014-04-10 17:30 UTC|newest]
Thread overview: 59+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-04-09 15:29 Wladimir
2014-04-09 15:37 ` Tamas Blummer
2014-04-09 15:41 ` Natanael
2014-04-09 15:54 ` Gregory Maxwell
2014-04-09 16:09 ` Thomas Voegtlin
2014-04-09 19:25 ` Wladimir
2014-04-10 6:04 ` Tamas Blummer
2014-04-10 11:09 ` Wladimir
2014-04-10 11:29 ` Mike Hearn
2014-04-10 11:32 ` Pieter Wuille
2014-04-10 11:43 ` Peter Todd
2014-04-10 11:50 ` Gregory Maxwell
2014-04-10 11:54 ` Peter Todd
2014-04-10 17:30 ` Tier Nolan [this message]
2014-04-11 16:54 ` Gregory Maxwell
2014-05-04 21:11 ` Tier Nolan
2014-04-09 17:31 ` Wladimir
2014-04-09 15:42 ` Brian Hoffman
2014-04-09 15:57 ` Gregory Maxwell
2014-04-09 16:09 ` Tamas Blummer
2014-04-09 15:47 ` Mark Friedenbach
2014-04-09 16:27 ` Tamas Blummer
2014-04-09 17:46 ` Peter Todd
2014-04-09 17:50 ` Tamas Blummer
2014-04-09 18:00 ` Mike Hearn
2014-04-09 18:19 ` Wladimir
2014-04-09 18:35 ` Justus Ranvier
2014-04-09 18:46 ` Wladimir
2014-04-09 18:50 ` Gregory Maxwell
2014-04-09 18:58 ` Justus Ranvier
2014-04-09 19:33 ` Gregory Maxwell
2014-04-09 20:12 ` slush
2014-04-09 20:31 ` slush
2014-04-09 20:36 ` Mark Friedenbach
2014-04-09 21:04 ` Gregory Maxwell
2014-04-09 20:37 ` Wladimir
2014-04-09 20:35 ` Wladimir
2014-04-09 20:50 ` slush
2014-04-09 20:55 ` Laszlo Hanyecz
2014-04-10 6:38 ` Mike Hearn
2014-04-10 6:50 ` Wladimir
2014-04-10 7:09 ` Mike Hearn
2014-04-10 9:33 ` Peter Todd
2014-04-10 7:10 ` Tamas Blummer
2014-04-10 9:17 ` Mike Hearn
2014-04-10 9:39 ` Tamas Blummer
2014-04-10 10:40 ` Mike Hearn
2014-04-10 10:44 ` Tamas Blummer
2014-04-10 11:36 ` Peter Todd
2014-04-10 11:45 ` Mike Hearn
2014-04-10 11:52 ` Peter Todd
2014-04-10 9:47 ` Peter Todd
2014-04-09 18:04 ` Peter Todd
[not found] ` <CA+s+GJBpvqqu=XEojyekx5su+JfYLwz+zsbo8L0=5t6s-_b33w@mail.gmail.com>
2014-04-09 17:35 ` [Bitcoin-development] Fwd: " Wladimir
2014-04-09 16:03 ` [Bitcoin-development] " Peter Todd
2014-04-09 17:33 ` Alex Mizrahi
2014-04-09 17:38 ` Wladimir
2014-04-09 17:38 ` Peter Todd
2014-04-09 18:35 ` Kevin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAE-z3OV4w+vQ0b6h9E+7cSyxkKENduyfHenhdF3q3-0i2chnGQ@mail.gmail.com \
--to=tier.nolan@gmail$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox