22:14 UTC

< December 2019 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

- Console
- #amber
- #apicula
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #etnaviv
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #lowempire
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #openwrt-devel
- #panfrost
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #solvespace
- #stellar
- #stellar-dev
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #trilema
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

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

<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)

<gmaxwell>
waxwing: aside, I don't get math formating in your blog posts unless I permit connecting to cloudflare. :(

<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 use wagner's algorithm too of course, but in this case there is a much more efficient algorithm for solving the problem

<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>
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>
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?

<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.

<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.

<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>
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)

<gmaxwell>
sipa: your comments made me think you don't think the weight-modifying annex will ever be done?