sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
LaserShark has quit []
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
proofofkeags has quit [Read error: Connection reset by peer]
tummy has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
Dizzle has quit [Quit: Leaving...]
Chris_Stewart_5 has joined #bitcoin-wizards
belcher has joined #bitcoin-wizards
jb55 has quit [Remote host closed the connection]
jb55 has joined #bitcoin-wizards
Dean_Guss has joined #bitcoin-wizards
proofofkeags has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 246 seconds]
proofofkeags has quit [Ping timeout: 256 seconds]
riclas has quit [Ping timeout: 256 seconds]
proofofkeags has joined #bitcoin-wizards
Belkaar_ has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 272 seconds]
peterrizzo_ has joined #bitcoin-wizards
peterrizzo_ has quit [Quit: peterrizzo_]
rusty has joined #bitcoin-wizards
tummy has quit []
zmnscpxj__ has joined #bitcoin-wizards
zmnscpxj_ has quit [Ping timeout: 240 seconds]
mengu has joined #bitcoin-wizards
mengu is now known as Guest6344
CryptoDavid has quit [Quit: Connection closed for inactivity]
proofofkeags has quit [Remote host closed the connection]
surja795 has quit [Remote host closed the connection]
rusty has quit [Ping timeout: 272 seconds]
surja795 has joined #bitcoin-wizards
DeanWeen has joined #bitcoin-wizards
Dean_Guss has quit [Ping timeout: 240 seconds]
surja795 has quit [Ping timeout: 264 seconds]
rusty has joined #bitcoin-wizards
gmaxwell has joined #bitcoin-wizards
<gmaxwell>
In a channel on video codec development I recently shared an idea for error recovery in live video streaming that avoids the overhead of sending keyframes.
<gmaxwell>
-----
<gmaxwell>
I had a cute idea for error recovery in a keyframeless CBR-ish realtime stream. Every X seconds (say 10), the decoder re-encodes
<gmaxwell>
a decoded frame from a couple frames ago. with some fast bit-exact encoder (can be at a higher bitrate than the stream).
<gmaxwell>
It decodes the re-encode, and then uses that recoded frame as its oldest reference frame. Then for every successive frame,
<gmaxwell>
it receives some FEC computed over the reencoded frame and every packet that comes after (using a rolling window FEC like
<gmaxwell>
some additional packet loss) it'll be able to recover everything in the window including the re-encoded reference.
<gmaxwell>
So this functions just like adding a bit of FEC to recover from small amounts of packet loss, but it can also recover
<gmaxwell>
from a total loss, but without ever sending a keyframe, and without the coding efficiency losses of a rolling keyframe.
<gmaxwell>
The added bitrate of the reencoded reference still benefits decoders which haven't lost their reference because it helps
<gmaxwell>
them recover from ordinary packet loss. Beyond complexity, the main downsides I see is that the decoder has to run
<gmaxwell>
fast enough to do these decodes, and also to catch up from behind when it finally recovers a bunch of past frames.
<gmaxwell>
-----
<gmaxwell>
Now take the above, and apply to bitcoin nodes syncing over a broadcast (like a satellite) with assumevalid-like security.
<gmaxwell>
Replace "keyframe" with UTXO set" "X seconds (say 10) with X blocks (say 4032)"... and it applies. It would let a node
<gmaxwell>
sync state from a broadcast stream after 4032 blocks, with a little over ~size(utxo set)/4032 additional data per block,
<gmaxwell>
and the additional data would also be 100% useful for recovering from packet loss for nodes that were in sync, so it's not
<gmaxwell>
wasted on peers that are in sync (like just slowly sending an old utxo set in the background would be).
rusty has quit [Quit: Leaving.]
rusty has joined #bitcoin-wizards
rusty has quit [Client Quit]
<BlueMatt>
gmaxwell: ah, thats clever. so, ie, for assumevalid+previous blocks download
<BlueMatt>
would allow you to effectively skip fetching any utxos you can get from recent blocks
<gmaxwell>
I suppose that too, but more my though was basically sending the UTXO set slowly in the background but without 'wasting' any bandwidth on it.
<gmaxwell>
In a context where you have two way connectivity and don't need FEC, it's not a win (or at least not a big win, as you note you could use it so that utxo from recent blocks could be left out of the next utxo snapshot)
<BlueMatt>
right. you'd have to send utxo updates correlated with the block itself
<BlueMatt>
right
<gmaxwell>
it was just interesting to me that utxo could be made zero overhead over ordinary FEC on blocks that keeps you from falling behind.
<BlueMatt>
wait wut
<BlueMatt>
sec
<BlueMatt>
wait, ok, so you're saying encode the utxo set in such a way to point the block data at the utxos encoded in the fec
<gmaxwell>
no.
<BlueMatt>
ok, then I'm confused
<zmnscpxj__>
the utxo set is used to seed the FEC?
<gmaxwell>
In a window of 4032 blocks, you FEC code: [serialized UTXO set, block10000, block10001, ..., block 14031]
<gmaxwell>
you don not transmit the serialized utxo set, you transmit the blocks, each with a little bit of FEC data.
<BlueMatt>
right. ok. yea, just gotta either init it with utxo set and receive blocks or have a bit extra fec in the block data to make sure you can recover if you dont have the utxo set
<gmaxwell>
Now, assuming you do not know the UTXO set... by the time you get to the end of that window, you've recieved enough FEC data to recover the whole utxo set (plus some small number of additional missing packets).
<gmaxwell>
Assuming you DID have the utxo set, you can use this FEC data to incrementally recover from missing packets in blocks as the come in.
<gmaxwell>
(or you could just use an arbritary random linear code, but decoding erasures in that has cubic complexity from gaussian elimination)
<gmaxwell>
the "simple" alternative to my scheme is that you just send 1/4032th of the old serialized UTXO set along with each block. Which works, but the bandwidth spend on that is entirely wasted for peers that knew the UTXO set.
<gmaxwell>
which is also why I say it's not applicable to non-broadcast mediums-- if you're not broadcasting, you send the utxo set to peers that need it and don't send it to ones that don't. :)
<BlueMatt>
well, i mean its still useful in that you can use it in the fec for that block
<BlueMatt>
just not across a long window
<gmaxwell>
oh so you're saying you could add 1/4032th of the UTXO set to each block, don't send it, but send FEC over the block and the UTXO set? That would work too, though you lose the long window advantage. For the sat broadcast long windows are preetty damn useful because bad weather can cause hours of poor connectivity.
<BlueMatt>
right
<gmaxwell>
it's pretty similar to the scheme I wanted to use for transaction lengths in fibre, but which you didn't implement-- I assume because the savings was too small.
<BlueMatt>
hmm. right, well in fibre you send the tx lengths in the initial header fec thing
<BlueMatt>
so looking up txid -> lengths means you'd have to send three fec data groups
<BlueMatt>
which would hurt
<gmaxwell>
BlueMatt: actually what I think it should have done is send length-fec words along with every payload FEC packet, because the need for the two are exactly proportional.
<gmaxwell>
e.g. with the header sent a couple length-fec words to get started, and then exact additional payload FEC packet sends avg_tx_per_packet length-fec along with them.
<BlueMatt>
E_NO_PARSE
<gmaxwell>
because like if you were missing 1 txn you'll only need 1/2 payload fec blocks to reconstruct. If you were missing 200 TXN and there are 20 txn per packet, you'll need 10 payload packets to recover. So you're good to go if there were 20 length FEC words with every payload packet.
<gmaxwell>
BlueMatt: the seperate fec groups isn't a problem because you need some constant fraction of each type, so you can just interleave them.
<gmaxwell>
like for a given block you need missing_txn words of length fec (to find your missing lengths) and missing_data words of payload to recover the missing transaction data. And the ratio of these is roughly a constant.
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
<BlueMatt>
wait, maybe I mis-parsed "it's pretty similar to the scheme I wanted to use for transaction lengths in fibre, but which you didn't implement-- I assume because the savings was too small."
<gmaxwell>
in fibre you just explicitly send all the lengths of the transactions using a varint.
<gmaxwell>
which is wastful, taking like 2-3 bytes per transaction even when 99-100% of those lengths are known already to the reciever.
<BlueMatt>
ohhhhhhh
<BlueMatt>
ok, now i get it
<BlueMatt>
right, you could do that, but you still have the issue that you cant start processing the tx data fec until after you've recovered the full tx length fec
<BlueMatt>
which sucks, cause fiber is not-irregularly cpu bound recovering the tx data fec
* BlueMatt
-> sleep
<gmaxwell>
sure you can, you don't have to give it data in order.
<gmaxwell>
you can give it the FEC as it comes in, then give it the mempool as soon as you have the lengths.
<gmaxwell>
and you'll have the lengths several packets before the data (if you set the ratios right)
<gmaxwell>
e.g. give the header the expected number of missing lengths, and give ntx more in each payload packet.
<gmaxwell>
I mean all it saves you is 3 bytes per txn, so I think for internet fibre you don't care.
<gmaxwell>
it makes a much bigger difference for minisketch based fibre.
bitdex has quit [Remote host closed the connection]
bitdex has joined #bitcoin-wizards
Guest6344 has quit []
AaronvanW has quit [Remote host closed the connection]
mterwoord has joined #bitcoin-wizards
Pasha has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
Pasha has quit []
AaronvanW has quit [Ping timeout: 256 seconds]
Pasha has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
marcoagner has joined #bitcoin-wizards
justanotheruser has quit [Ping timeout: 256 seconds]
justanotheruser has joined #bitcoin-wizards
mterwoord has quit []
AaronvanW has quit [Ping timeout: 240 seconds]
mryandao has quit [Remote host closed the connection]
mryandao has joined #bitcoin-wizards
Mikaku1 has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
riclas has joined #bitcoin-wizards
zmnscpxj__ has quit [Ping timeout: 240 seconds]
surja795 has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 240 seconds]
roconnor_ has quit [Ping timeout: 264 seconds]
AaronvanW has joined #bitcoin-wizards
bitdex has quit [Ping timeout: 240 seconds]
bitdex has joined #bitcoin-wizards
surja795 has joined #bitcoin-wizards
DeanWeen has quit [Ping timeout: 240 seconds]
AaronvanW has quit [Ping timeout: 272 seconds]
gribble has quit [Read error: Connection reset by peer]
surja795 has quit [Remote host closed the connection]
gribble has joined #bitcoin-wizards
surja795 has joined #bitcoin-wizards
surja795_ has joined #bitcoin-wizards
surja795 has quit [Read error: Connection reset by peer]
surja795_ has quit [Ping timeout: 256 seconds]
dllud_ has quit [Read error: Connection reset by peer]
dllud has joined #bitcoin-wizards
shush has joined #bitcoin-wizards
Mikaku1 has quit []
shush has quit [Ping timeout: 260 seconds]
peterrizzo has joined #bitcoin-wizards
peterrizzo has quit [Client Quit]
surja795 has joined #bitcoin-wizards
<yanmaani>
I know that Proof of Stake is generally impossible
<yanmaani>
but would it be possible for a bitcoin sidechain?
<yanmaani>
stake real bitcoins, use the real bitcoin chain's block hashes to select validator, etc
AaronvanW has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 264 seconds]
surja795 has joined #bitcoin-wizards
Spanktar has joined #bitcoin-wizards
surja795_ has joined #bitcoin-wizards
surja795 has quit [Read error: Connection reset by peer]
Chris_Stewart_5 has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
queip has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
belcher has joined #bitcoin-wizards
Spanktar has quit []
peterrizzo has joined #bitcoin-wizards
peterrizzo has quit [Quit: peterrizzo]
gmaxwell has left #bitcoin-wizards [#bitcoin-wizards]
dfkt has joined #bitcoin-wizards
riyasingh has joined #bitcoin-wizards
riyasingh has quit [Client Quit]
wk057 has quit [Read error: Connection reset by peer]
zmnscpxj__ has joined #bitcoin-wizards
riya has joined #bitcoin-wizards
morcos has quit [Remote host closed the connection]
morcos has joined #bitcoin-wizards
wk057 has joined #bitcoin-wizards
bitdex has quit [Remote host closed the connection]
bitdex has joined #bitcoin-wizards
riyasingh has joined #bitcoin-wizards
riyasingh has left #bitcoin-wizards [#bitcoin-wizards]
riyasingh has joined #bitcoin-wizards
riyasingh has quit [Client Quit]
AaronvanW has quit [Ping timeout: 264 seconds]
AaronvanW has joined #bitcoin-wizards
CryptoDavid has joined #bitcoin-wizards
dgenr8 has quit [Remote host closed the connection]
dgenr8 has joined #bitcoin-wizards
dfkt has quit []
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
mryandao has quit [Remote host closed the connection]
mryandao has joined #bitcoin-wizards
gdude2002 has joined #bitcoin-wizards
surja795_ has quit [Remote host closed the connection]
surja795 has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 272 seconds]
tromp has quit [Ping timeout: 240 seconds]
tromp has joined #bitcoin-wizards
marsh4dow has joined #bitcoin-wizards
riya has quit [Quit: Connection closed for inactivity]
tromp has quit [Remote host closed the connection]
marsh4dow has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
surja795 has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 246 seconds]
tromp has quit [Remote host closed the connection]
surja795 has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 260 seconds]
tromp has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
DeanWeen has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
belcher has quit [Remote host closed the connection]
tromp has quit [Remote host closed the connection]
gdude2002 has quit []
surja795 has quit [Remote host closed the connection]
belcher has joined #bitcoin-wizards
surja795 has joined #bitcoin-wizards
drybjed1 has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
shesek has quit [Ping timeout: 264 seconds]
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
proofofkeags has joined #bitcoin-wizards
shesek has quit [Ping timeout: 264 seconds]
AaronvanW has quit [Ping timeout: 246 seconds]
AaronvanW has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 246 seconds]
TheoStorm has quit [Quit: Leaving]
tromp has quit [Remote host closed the connection]
TheoStorm has joined #bitcoin-wizards
DeanWeen has quit [Remote host closed the connection]
DeanWeen has joined #bitcoin-wizards
AaronvanW has quit []
proofofkeags has quit [Remote host closed the connection]
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]