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
Chris_Stewart_5 has quit [Quit: WeeChat 0.4.2]
<dgenr8>
The third equation on page 6 differs from the Nakamoto formula, yet claims to restate it. It is off by one in the upper summation index.
airbreather has quit [Read error: Connection reset by peer]
airbreather has joined #bitcoin-wizards
<dgenr8>
Ah, doesn't matter. When k=z the addend is zero.
MaxSan has quit [Read error: Connection reset by peer]
MaxSan has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
cluckj has joined #bitcoin-wizards
chjj has quit [Remote host closed the connection]
oleganza has quit [Quit: oleganza]
deadalnix has quit [Ping timeout: 260 seconds]
HostFat_ has joined #bitcoin-wizards
HostFat__ has quit [Ping timeout: 260 seconds]
EvilHero_ has joined #bitcoin-wizards
EvilHero_ has quit [Max SendQ exceeded]
jtimon has quit [Ping timeout: 240 seconds]
priidu has quit [Ping timeout: 256 seconds]
CheckDavid has quit [Quit: Connection closed for inactivity]
oleganza has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
PRab has joined #bitcoin-wizards
PRab has quit [Quit: ChatZilla 0.9.93 [Firefox 51.0.1/20170125094131]]
roasbeef_ is now known as roasbeef
todaystomorrow has quit [Ping timeout: 264 seconds]
rusty2 has quit [Ping timeout: 240 seconds]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
psztorc_ has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
psztorc has quit [Ping timeout: 264 seconds]
pro has quit [Quit: Leaving]
WungFu has quit [Ping timeout: 240 seconds]
recola has quit [Ping timeout: 240 seconds]
bsm1175321 has quit [Remote host closed the connection]
bsm1175321 has joined #bitcoin-wizards
rusty2 has joined #bitcoin-wizards
TheSeven has quit [Ping timeout: 258 seconds]
TheSeven has joined #bitcoin-wizards
oleganza has quit [Quit: oleganza]
oleganza has joined #bitcoin-wizards
rusty2 has quit [Ping timeout: 245 seconds]
saintromuald has quit [Ping timeout: 245 seconds]
Ylbam has joined #bitcoin-wizards
kankles has joined #bitcoin-wizards
saintromuald has joined #bitcoin-wizards
edvorg has joined #bitcoin-wizards
d9b4bef9 has quit [Ping timeout: 260 seconds]
d9b4bef9 has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
fibonacci has joined #bitcoin-wizards
MoALTz has joined #bitcoin-wizards
saintromuald has quit [Ping timeout: 240 seconds]
Oizopower has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
CrazyLoaf has quit [Quit: Connection closed for inactivity]
MaxSan has quit [Ping timeout: 245 seconds]
MaxSan has joined #bitcoin-wizards
edvorg has quit [Ping timeout: 260 seconds]
Giszmo has quit [Read error: Connection reset by peer]
saintromuald has joined #bitcoin-wizards
CrazyLoaf has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 256 seconds]
Guyver2 has joined #bitcoin-wizards
mountaingoat has quit [Ping timeout: 252 seconds]
MoALTz has quit [Ping timeout: 240 seconds]
andytoshi has quit [Ping timeout: 268 seconds]
mountaingoat has joined #bitcoin-wizards
andytoshi has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
MoALTz has joined #bitcoin-wizards
Oizopower has quit [Quit: Connection closed for inactivity]
MoALTz_ has joined #bitcoin-wizards
MoALTz has quit [Ping timeout: 240 seconds]
laurentmt has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
MaxSan has left #bitcoin-wizards [#bitcoin-wizards]
fibonacci has quit [Quit: Connection closed for inactivity]
chjj has quit [Ping timeout: 260 seconds]
chjj has joined #bitcoin-wizards
lclc has quit [Ping timeout: 264 seconds]
deadalnix has joined #bitcoin-wizards
chjj has quit [Ping timeout: 255 seconds]
MaxSan has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
lclc has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
mountaingoat has quit [Ping timeout: 240 seconds]
mountaingoat has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
CrazyLoaf has quit [Quit: Connection closed for inactivity]
deadalnix has quit [Remote host closed the connection]
deadalnix has joined #bitcoin-wizards
MaxSan has quit [Ping timeout: 264 seconds]
dnaleor has quit [Quit: Leaving]
Guyver2 has quit [Quit: :)]
gielbier has quit [Ping timeout: 276 seconds]
sn0wmonster has quit [Quit: ¯\_(ツ)_/¯]
dnaleor has joined #bitcoin-wizards
edvorg has joined #bitcoin-wizards
WungFu has quit [Ping timeout: 276 seconds]
Giszmo has joined #bitcoin-wizards
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
CheckDavid has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
sn0wmonster has joined #bitcoin-wizards
WungFu has quit [Ping timeout: 260 seconds]
pro has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
sn0wmonster has quit [Ping timeout: 260 seconds]
BlueMatt has quit [Excess Flood]
WungFu has quit [Quit: Leaving]
BlueMatt has joined #bitcoin-wizards
MaxSan has joined #bitcoin-wizards
pedrovian_ has joined #bitcoin-wizards
pedrovian1 has quit [Ping timeout: 240 seconds]
schmidty has quit [Ping timeout: 240 seconds]
Ylbam has quit [Quit: Connection closed for inactivity]
sn0wmonster has joined #bitcoin-wizards
kanzure has quit [Ping timeout: 240 seconds]
kanzure has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
neha has joined #bitcoin-wizards
gielbier has joined #bitcoin-wizards
<tromp_>
downside of replacing difficulty by cumulative version is that you need full 256 bit precision
<andytoshi>
i think this is true
<tromp_>
but that is small price to pay. and gives less worries about frequent more fine grained difficulty adjustments
<andytoshi>
128 bits is probably fine, or 64 even
<tromp_>
yes, depending on how much hash power could scale over lifetime
<andytoshi>
regarding your successors-commit-to-successors scheme, does this mean basically each block in the compact chain has two headers?
<andytoshi>
the "real" one and then its predecessor which has all the work
<tromp_>
yes, to witness the whole compact chain, you'll get a sequence of header pairs
<andytoshi>
does this create an attack wherein i take any high-work block from any part of any chain and build on that?
<tromp_>
the first in each pair has the lucky pow, and the second the commitment to both the first and the previous pair
<andytoshi>
right, but the first doesn't commit to anything verifiable
<tromp_>
that attack wld work similarly on your merkle tree
<tromp_>
wouldnt it?
<andytoshi>
it doesn't, because with the merkle tree the big work is committing to the predecessor
<tromp_>
but the commit of the successor also commits to the whole history
<andytoshi>
here you're just taking arbitrary work that you didn't have to do yourself (you could have found it anywhere) and then using that as a ticket to skip
<tromp_>
in both cases there is a compact chain that is commited to
<andytoshi>
yes, but in my scheme the compact chain has a ton of work committing to each link
MaxSan has quit [Ping timeout: 258 seconds]
<andytoshi>
here you have little work which commits (a) to the compact chain, and (b) to a bunch of work
<tromp_>
but (a) directly commits to (b)
<andytoshi>
that's fine, but unless (b) commits to the compact chain, its work doesn't prove anything about the compact chain
<tromp_>
hmm, this is a little mind spinning. let me ponder it some more
<andytoshi>
heh, yeah, it took me way longer than i'd expected to convince myself that the merkle tree thing worked the way that i'd handwaved it to
<tromp_>
you're saying you could take a compact chain (b) and fake all the successors forming (a), which does indeed seem to be a problem:(
<tromp_>
or take any set of high pow blocks as (b)
<andytoshi>
yeah, potentially even from other chains
oleganza has quit [Quit: oleganza]
MoALTz_ is now known as MoALTz
<tromp_>
btw, your effective difficulties are just sums of difficulties of partitioning block ranges, right?
<andytoshi>
if i'm understanding you correctly, yes
<bsm117532>
tromp if I understand correctly, you want to commit to the luckiest block in history, and the most recent block as a pair?
<bsm117532>
If instead you commit to a log(height) sized list of blocks representing the luckiest blocks in each range, you've committed to the whole history and the PoW in a verifiable way. Truncating log(height) to 2 seems to introduce problems...
<bsm117532>
(or as discussed yesterday, some subset of the luckiest blocks in each range -- to reduce variance)
<bsm117532>
e.g. at height 1153 = 0b10010000001 you'd commit to the luckiest 3 blocks in the first 1024, the luckiest 2 blocks in the next 128, and the most recent block, where the numbers 3 and 2 need to be tuned kill attacks that take advantage of variance.
<tromp_>
these are all variations of the high value hash highway proposed years ago, but andrew's formulation is the cleanest so far
<bsm117532>
Andrew's formulation certainly works AFAICT. My complaint about it is that the PoW cannot be verified without the entire history, and I think there's a way to reformulate it into a log(height) sized list per block, which allows direct verification of the PoW -- thus allowing clients to drop history.
<bsm117532>
e.g. given a merging rule (d1+d2, hash(h1+h2)), there's no way to verify that the combined difficulties d1+d2 corresponds to hash(h1+h2) unless you have the leaves.
<tromp_>
we imagine using this for pows with large witnesses (100s of bytes instead of just a nonce), in which case a selfcontained powopow would be too big
<bsm117532>
the merging rule (min(d1,d2), hash corresponding to min(d1,d2)) does allow for direct verification.
<bsm117532>
tromp_ can you elaborate? I'm not sure what you mean...
<tromp_>
your disire to drop history sounded to me like you want to have self-contained powopow that dont need to query early blocks
<bsm117532>
correct.
<tromp_>
so you want to include logarithmic number of proofs in each block?
chjj has quit [Remote host closed the connection]
<tromp_>
or just commitment to them?
<bsm117532>
Just commitments to them.
<bsm117532>
Full nodes can then feed this log list to light clients.
<tromp_>
this might suffer from same problem that my compact successor chain had...
<uiuc-slack>
<amiller> i think you are reinventing the scheme in the popow paper
<bsm117532>
that is, I could take lucky hashes from anywhere, construct a fake commitment, and feed it to light clients?
<bsm117532>
amiller: I most certainly am. I'm too lazy to read.
<uiuc-slack>
<amiller> ok, fair enough, keep going then :slightly_smiling_face:
<bsm117532>
;-)
<bsm117532>
tromp_ fake commitments like that would only work if the light client has no history at all. If the light client queries for the latest block on a semi-regular basis, the oldest lucky blocks will remain the same.
<bsm117532>
Also, by including <n> lucky blocks from the oldest range to reduce variance, some of those lucky blocks will still be lucky when the next power of 2 rolls around in log_2(height).
<tromp_>
so a blockchain design might end up using two block merkle trees; one for all blocks, and one for dominating blocks (what i wld call blocks in compact chain)
<bsm117532>
Ah yes, the "hash highway" is a Merkle skip list...amiller showed me that a while ago...
<tromp_>
yes bsm117532 yes, but we shld prefer foolproof solutions over ones that are probably secure with enough extra chceking
<bsm117532>
tromp_ of course. I'm brainstorming. ;-)
<tromp_>
to witness the compact chain within a merkle tree on all blocks, you'd need a size log^2(n) proof of witness paths
<tromp_>
so the separate merkle tree seems worth the effort
BashCo_ has quit [Read error: Connection reset by peer]
Sosumi has joined #bitcoin-wizards
<bsm117532>
Wait...let me define V(n) to be the number of lucky hashes presented at height 2^n to reduce variance. Assuming V(n) < V(n+1), ALL of the lucky hashes will already have been seen by a light client updating his wallet.
<tromp_>
btw, there is some small but non-trivial chance that at some point the compact chain consists of only 3 nodes; genesis, an extrememly lucky pow, and its successor witnessing the luck
<bsm117532>
In the event there's a new lucky hash since the last block header update, the light client could directly query for the log(n) list of lucky hashes at that height.
<bsm117532>
tromp_ In your scheme that would happen any time height = 2^n for integer n.
<bsm117532>
And at those points you'd have maximal variance...
chjj has joined #bitcoin-wizards
<tromp_>
i'm sorry bsm117532; i'm too happy with andrew's powow design to seriously study variance based alternatives:(
<bsm117532>
heheee I need to study that more carefully.
Guest37379 has joined #bitcoin-wizards
Guest37379 is now known as Davasny
<tromp_>
btw, andytoshi, it seems that the compact chain witnesses at least half of the cumulative difficulty of the entire chain, correct?
<tromp_>
i was trying to remember if the compact chain witnesses all of the work or just the majority. guess i need to read those theorems in detail to see which statement is more correct
<tromp_>
btw, andytoshi, is that the most up-to-date version of your paper?
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
Ylbam has joined #bitcoin-wizards
CheckDavid has quit [Quit: Connection closed for inactivity]
abpa has joined #bitcoin-wizards
reginaldo has joined #bitcoin-wizards
reginaldo has quit [Client Quit]
reginaldo_ has joined #bitcoin-wizards
droark has joined #bitcoin-wizards
baarvader has joined #bitcoin-wizards
<tromp_>
andytoshi, i think your lemma 2 is false
<tromp_>
expected #blocks to achieve sum-of-difficulty >= D is less than D
<tromp_>
but expected #blocks to find *first* block of difficulty >= D is D
<tromp_>
here i use difficulty=hashspacesize/hash
<tromp_>
or maybe i misunderstood the statement...
<andytoshi>
tromp_: "expected #blocks to find *first* block of difficulty >= D is D" seems meaningless
<andytoshi>
how are you counting blocks?
<andytoshi>
the lemma doesn't seem to talk about counting blocks at all
<tromp_>
i mean hash attempts
<andytoshi>
oh i see. let me think about this, i still think i'm correct here
<tromp_>
i'm just considering successive hash attempts and ignoring minimum required difficulty
<andytoshi>
yep understood
<tromp_>
for instance it takes expected 6 die throws to get a 6
<tromp_>
but getting sum difficulty to be 6 required fewer throws
<andytoshi>
the claim is that rolling three evens should take as much time as rolling one six
<andytoshi>
and those both have expected 6 rolls
<andytoshi>
because there are 3 times as many evens as there are sixes on a die
<tromp_>
that is true
<tromp_>
but in lemma 2, every failed attempts still contributes to sum
<Jeremy_Rand[m]>
Has anyone proposed/investigated the idea of a merge-mined chain in which the child chain is re-orged if and only if the parent chain is re-orged? (I.e. the block headers of the parent chain are used to decide the most-work rule of the child chain.)
<Jeremy_Rand[m]>
It seems like an obvious enough idea that I assume someone has thought of it
<andytoshi>
tromp_: ah i see
<andytoshi>
if i ask you to show me "3 evens or one six" that'll take you less than 6 tries?
<andytoshi>
i guess so
<tromp_>
sure
<andytoshi>
interesting
<tromp_>
just like with coin flipping, two anything or one head takes expected less than 2 tries
<andytoshi>
hmmm
<tromp_>
oops
<tromp_>
that is not correct analogy
<tromp_>
since anything has difficulty 0
atgreen has joined #bitcoin-wizards
<tromp_>
but expected 6 throws for 1st six includes many events with more than 3 evens
<tromp_>
so stopping on 3 evens has to lower expectancy
<andytoshi>
yeah, it will take 5 tries on average
<tromp_>
3 state markov chain:)
<andytoshi>
(easier to think about stopping on sixes; then if you roll five dice without sixes, each has 3/5 chance of being even and there you go)
<andytoshi>
i'd bet if you built the markov chain and played it forward you'd get the same result with a lot more work :P
<andytoshi>
so this is shitty. what is the real expected number of attempts here?
<andytoshi>
if it's something nice like "twice as many" or "e times as many" then *shrug*, but if it squares them or something awful i'm going to be sad
<tromp_>
hmm, it doesn't seem to be 5
<andytoshi>
oh, i was calculating "if you roll 5 dice with no sixes, what is the expected number of evens?" to which the answer is 3, but i guess that's not right
<tromp_>
anyway, seems Lemma 2 needs to have different outcome for expected #attempts to achieve some total eff. difficulty
<tromp_>
it's going to be somwhere between D/2 and D
<tromp_>
presumably
<tromp_>
afk to dr's appt...
<andytoshi>
np i've also gotta take off for a couple hours
<andytoshi>
but you're saying i'm wrong by at worst a factor of 2?
<tromp_>
the way you compute compact chain, you leave out at most half the sum-difficultyu
<andytoshi>
great, so if my compact chain is twice as long i'm still ok?
<andytoshi>
i have size 2log instead of log
<tromp_>
you alrd picked the luckiest blocks, you cannot pick another same size set that's as lucky
<tromp_>
i think perhaps the best you can do is a O(log(n)) sized subchain that proves 1-eps of the work
<andytoshi>
that sucks
<andytoshi>
sure i can't just define "effective difficulty" as 1/2 its current definition?
MaxSan has joined #bitcoin-wizards
oleganza has joined #bitcoin-wizards
<bsm117532>
"the claim is that rolling three evens should take as much time as rolling one six" -- that's not true. The former has a probability P=1/2 to roll an even, three rolls has probability P^3=1/8 to get all evens while one six has probability 1/6.
deadalnix has quit [Ping timeout: 260 seconds]
blackwraith has joined #bitcoin-wizards
reginaldo_ has quit [Ping timeout: 240 seconds]
sausage_factory has joined #bitcoin-wizards
blackwraith has quit [Ping timeout: 252 seconds]
reginaldo_ has joined #bitcoin-wizards
none has joined #bitcoin-wizards
none is now known as Guest58074
Aranjedeath has quit [Quit: Three sheets to the wind]
MaxSan has quit [Ping timeout: 245 seconds]
aalex has joined #bitcoin-wizards
Aranjedeath has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
reginaldo_ has quit [Quit: Leaving]
rusty2 has joined #bitcoin-wizards
rusty2 has quit [Ping timeout: 276 seconds]
lclc has quit [Ping timeout: 260 seconds]
BashCo has joined #bitcoin-wizards
deadalnix has joined #bitcoin-wizards
dnaleor has quit [Ping timeout: 276 seconds]
fibonacci has joined #bitcoin-wizards
fibonacci is now known as Guest20395
Guest20395 is now known as fibonaccicoin
fibonaccicoin has quit [Changing host]
fibonaccicoin has joined #bitcoin-wizards
fibonaccicoin has joined #bitcoin-wizards
rusty2 has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
deadalnix has quit [Ping timeout: 252 seconds]
CrazyLoaf has joined #bitcoin-wizards
Buckyy has quit [Quit: ereet]
deadalnix has joined #bitcoin-wizards
buckowski has joined #bitcoin-wizards
rusty2 has quit [Ping timeout: 260 seconds]
JHistone has joined #bitcoin-wizards
JHistone has quit [Client Quit]
pero has joined #bitcoin-wizards
<maaku>
Jeremy_Rand[m]: isn't that how merged mining works, generally?
sausage_factory has quit [Ping timeout: 240 seconds]
<maaku>
"the block headers of the parent chain are used to decide the most-work rule of the child chain" <-- as far as I'm aware, this is vanilla merge mining
Guyver2 has joined #bitcoin-wizards
zephyrbtc has joined #bitcoin-wizards
Guyver2 has quit [Remote host closed the connection]
aj_ is now known as aj
dnaleor has quit [Quit: Leaving]
chjj has quit [Ping timeout: 240 seconds]
pero has quit [Ping timeout: 240 seconds]
pero has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
meZee has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
<tromp_>
bsm11753 expected #rolls to get k evens = 2k
<tromp_>
so for k=3 that is indeed identical to the expected #throws to get a 6
Noldorin has joined #bitcoin-wizards
baarvader has quit []
rusty2 has joined #bitcoin-wizards
zephyrbtc has quit [Ping timeout: 260 seconds]
face has quit [Ping timeout: 258 seconds]
face has joined #bitcoin-wizards
Davasny has quit [Remote host closed the connection]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
zephyrbtc has joined #bitcoin-wizards
chjj has quit [Remote host closed the connection]
dnaleor has quit [Quit: Leaving]
aalex has quit [Ping timeout: 260 seconds]
dnaleor has joined #bitcoin-wizards
fibonaccicoin has quit [Quit: Connection closed for inactivity]
Giszmo has quit [Ping timeout: 240 seconds]
tromp has quit [Read error: Connection reset by peer]