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
AIM` has quit []
slivera has quit [Quit: Leaving]
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
head_victim has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 268 seconds]
ddustin has joined #bitcoin-wizards
ddustin has quit [Read error: Connection reset by peer]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 260 seconds]
luke-jr has quit [Ping timeout: 268 seconds]
luke-jr has joined #bitcoin-wizards
dongcarl has quit [Quit: The Lounge - https://thelounge.chat]
dongcarl has joined #bitcoin-wizards
dongcarl has quit [Client Quit]
dongcarl has joined #bitcoin-wizards
rjected has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 268 seconds]
marcoagner has quit [Ping timeout: 268 seconds]
Belkaar_ has quit [Ping timeout: 260 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
luke-jr has quit [Quit: ZNC - http://znc.sourceforge.net]
luke-jr has joined #bitcoin-wizards
head_victim has quit []
votesmith has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
dholbach has joined #bitcoin-wizards
alferz has joined #bitcoin-wizards
DeanGuss has joined #bitcoin-wizards
alferz has quit [Ping timeout: 255 seconds]
DeanGuss has quit [Remote host closed the connection]
DeanGuss has joined #bitcoin-wizards
dholbach has quit []
luke-jr has quit [Quit: ZNC - http://znc.sourceforge.net]
luke-jr has joined #bitcoin-wizards
hardaker has joined #bitcoin-wizards
BlueMatt has quit [Ping timeout: 245 seconds]
BlueMatt has joined #bitcoin-wizards
dr-orlovsky has joined #bitcoin-wizards
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
dr-orlovsky has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
slivera has joined #bitcoin-wizards
kabaum has quit [Ping timeout: 248 seconds]
hardaker has quit []
ksamak has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
<sipa> waxwing: in https://joinmarket.me/blog/blog/avoiding-wagnerian-tragedies/ you mention using XOR as a way to combine the results of hash functions... if yiu actually use xor you can do much better than wagner's algorithm by treating the system as a set of linear equations over GF(2)
<sipa> so it's just a matrix inversion with O(n) hashes
AaronvanW has joined #bitcoin-wizards
jonatack has quit [Ping timeout: 260 seconds]
luke-jr has quit [Quit: ZNC - http://znc.sourceforge.net]
luke-jr has joined #bitcoin-wizards
marcoagner has joined #bitcoin-wizards
jonatack has joined #bitcoin-wizards
<gmaxwell> waxwing: aside, I don't get math formating in your blog posts unless I permit connecting to cloudflare. :(
jonatack has quit [Ping timeout: 265 seconds]
jonatack has joined #bitcoin-wizards
Kiminuo has joined #bitcoin-wizards
Kiminuo has quit [Read error: Connection reset by peer]
Kiminuo has joined #bitcoin-wizards
<waxwing> gmaxwell, oh. well that's not good, sorry.
<waxwing> sipa, sounds interesting, though i didn't entirely get it. got a link i could read?
Dean_Guss has joined #bitcoin-wizards
DeanGuss has quit [Ping timeout: 240 seconds]
<sipa> waxwing: i think i learned this from the elliptic curve multiset hash paper
<sipa> waxwing: basically if you want to solve the generalized birthday problem, and the operation you use to combime hashes is bitwise xor
<sipa> you can just generate a random 256 bit hashes
<sipa> make them the rows of a GF(2) 256*256 matrix
<waxwing> "MuHash" .. get your lawyers on them :)
<sipa> invert that matrix, and multiply it with your desired hash sum vector
<sipa> this gives you a bit vector that identifes the subset of hashes to combine
<sipa> you can use wagner's algorithm too of course, but in this case there is a much more efficient algorithm for solving the problem
<waxwing> this paper is interesting, i like these points about homomorphic hashes
<waxwing> so thanks. i'll have a read and ask you if i still don't get it (though it sounds intuitively like it makes sense).
<sipa> so wagner's algorithm is really only optimal when your hash combination function defines a group that doesn't split into many tiny subgroups
<sipa> which is the case when you're working over GF(p)
ksamak has quit []
<sipa> waxwing: there is a lot of interesting stuff in that paper
<sipa> i hope i'm not misremembering that it's there that i read about xhash (xor of set hashes) being so trivial to break
<waxwing> it doesn't kind of violate the thread of my blog post, i was mainly trying to reach an understanding of the inapplicability of this attack to discrete-log-hard groups, it seemed like a really interesting thing to investigate.
<waxwing> that there's a substantially better way to do it in certain cases is definitely interesting though.
<sipa> yeah, agree - it's not wrong, just not a perfect example
<gmaxwell> it's a reason though perhaps to just avoid using xor as your leading example. :P
<gmaxwell> if you were to do a revision
<waxwing> gmaxwell, sure. but i was literally following the paper.
<sipa> random vaguely related fact: did you know that the probability that a GF(2) n*n matrix is invertible comverges rapidly to a constant 0.288788... as n grows?
<waxwing> thanks for the comments though, it's great to get some input on it.
<gmaxwell> sipa: I seem to recall discussing with you the more general case of other fields before.
<gmaxwell> prod(1-0.5^n,1,inf) might be more informative than the constant. :P
<waxwing> lol yeah i just found the proof. it's irritatingly simple.
<waxwing> found as in found on web, not worked it out :)
<sipa> yeah
<sipa> but this means that to solve generalized birthday for xhash you literally just need 3.5 ish iterations, independently of how large the hash is
<gmaxwell> it's not as simple to figure out how many additional you need to draw before you can find a subset thats invertable.
<sipa> yeah, just replace all of them
<gmaxwell> lame upper bound. :P
<sipa> you can do it row by row
<gmaxwell> usually you'll only fail by a single linear dependance, and can fix just that one.
<sipa> every new hash you add has to be linearly independent of the ones you have before
<sipa> if it isn't, replace just the last one
<sipa> and then continue
<gmaxwell> the same inversion trick should work for arbritary fields so long as you can include an entry an arbritary (potentially very large) number of times.
slivera has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
<sipa> gmaxwell: invertibility for matrices over fields larger than gf(2) is harder as you need to account for linear combinations over all vectors
<gmaxwell> Yes, but they are invertable even more often than GF(2).
Guyver2 has joined #bitcoin-wizards
<gmaxwell> kanzure: https://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2019-12-16-bip-taproot-bip-tapscript/ "You can add or remove it, as long as your transaction has signatures." should be can't.
<gmaxwell> (there were one or two other backwards things earlier but I didn't think they were worth mentioning)
jonatack has quit [Excess Flood]
jonatack has joined #bitcoin-wizards
jonatack has quit [Ping timeout: 268 seconds]
<sipa> ^ indeed
jonatack has joined #bitcoin-wizards
abian1 has joined #bitcoin-wizards
<gmaxwell> sipa: your comments made me think you don't think the weight-modifying annex will ever be done?
<gmaxwell> one of the other edits was "Other witness versions remain encumbered," should be unencumbered.
jonatack has quit [Read error: Connection reset by peer]
Chris_Stewart_5 has joined #bitcoin-wizards
<sipa> gmaxwell: i don't know if we'll ever have a need for it
<sipa> as it depends on having some opcode with a high expected cpu cost to witness size
TheoStorm has quit [Ping timeout: 258 seconds]
Guyver2_ has joined #bitcoin-wizards
Guyver2 has quit [Ping timeout: 264 seconds]
TheoStorm has joined #bitcoin-wizards
pinheadmz_ has joined #bitcoin-wizards
pinheadmz has quit [Read error: Connection reset by peer]
pinheadmz_ is now known as pinheadmz
abian1 has quit []
Guyver2__ has joined #bitcoin-wizards
Guyver2_ has quit [Ping timeout: 264 seconds]
RandIter has joined #bitcoin-wizards
jonatack has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 268 seconds]
votesmith has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
luke-jr has quit [Quit: ZNC - http://znc.sourceforge.net]
luke-jr has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
votesmith has quit [Ping timeout: 258 seconds]
votesmith has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 268 seconds]
<kanzure> fixed those errors
votesmith has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 260 seconds]
dr-orlovsky has joined #bitcoin-wizards
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
Chris_Stewart_5 has joined #bitcoin-wizards
pinheadmz_ has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 260 seconds]
pinheadmz has quit [Ping timeout: 260 seconds]
pinheadmz_ is now known as pinheadmz
TheoStorm has quit [Quit: Leaving]
pinheadmz_ has joined #bitcoin-wizards
pinheadmz has quit [Ping timeout: 268 seconds]
pinheadmz_ is now known as pinheadmz
RandIter has quit []
Chris_Stewart_5 has quit [Ping timeout: 268 seconds]
TheoStorm has joined #bitcoin-wizards
TheoStorm has quit [Remote host closed the connection]
wilsonk-laptop has joined #bitcoin-wizards
dr-orlovsky has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
TheoStorm has quit [Remote host closed the connection]
TheoStorm has joined #bitcoin-wizards
justanotheruser has joined #bitcoin-wizards
TheoStorm has quit [Remote host closed the connection]
dr-orlovsky has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
dr-orlovsky has joined #bitcoin-wizards
rottensox has quit [Quit: Bye]
votesmith has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 260 seconds]
Guyver2_ has joined #bitcoin-wizards
Guyver2__ has quit [Ping timeout: 268 seconds]
votesmith has joined #bitcoin-wizards
gambpang has quit [Quit: ZNC 1.6.3+deb1+xenial0 - http://znc.in]
wraithm has quit [Quit: ZNC 1.6.3+deb1+xenial0 - http://znc.in]
gambpang has joined #bitcoin-wizards
wraithm has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
TheoStorm has quit [Remote host closed the connection]
wraithm has quit [Client Quit]
gambpang has quit [Quit: ZNC 1.6.3+deb1+xenial0 - http://znc.in]
gambpang has joined #bitcoin-wizards
wraithm has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 265 seconds]
votesmith has quit [Ping timeout: 260 seconds]
votesmith has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 260 seconds]
votesmith has joined #bitcoin-wizards
wilsonk-laptop has quit []
TheoStorm has joined #bitcoin-wizards
wright has joined #bitcoin-wizards
rjected has quit [Quit: WeeChat 2.6]
votesmith has quit [Ping timeout: 268 seconds]
rjected has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
luke-jr has quit [Ping timeout: 268 seconds]
rjected has quit [Quit: WeeChat 2.6]
rjected has joined #bitcoin-wizards
rjected has quit [Client Quit]
rjected has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 260 seconds]
luke-jr has joined #bitcoin-wizards
TheoStorm has quit [Remote host closed the connection]
Chris_Stewart_5 has joined #bitcoin-wizards
Guyver2_ has quit [Quit: Going offline, see ya! (www.adiirc.com)]
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
votesmith has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 258 seconds]
TheoStorm has joined #bitcoin-wizards
votesmith has joined #bitcoin-wizards
slivera has joined #bitcoin-wizards
Kiminuo has quit [Ping timeout: 268 seconds]
laurentmt has quit [Quit: laurentmt]
Logicwax has quit [Ping timeout: 260 seconds]
belcher has quit [Quit: Leaving]
Logicwax has joined #bitcoin-wizards
votesmith has quit [Ping timeout: 260 seconds]