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
asynk has joined #bitcoin-wizards
<maaku>
nicolagreco: you can get SPV-level assurance with commitments to the current state
<maaku>
also mimblewimble is non-pairing way to get the same, for a limited set of problems
polyclef_ has joined #bitcoin-wizards
<amiller>
using "cut-and-choose" directly over all the state updates is only good for showing that a large fraction of the steps are valid, not that the whole thing is valid
Ylbam has quit [Quit: Connection closed for inactivity]
<amiller>
thats a pretty cool list of all the approaches though! i really like this channel still :)
JackH_ has quit [Ping timeout: 260 seconds]
oleganza has quit [Quit: oleganza]
<bsm1175321>
nicolagreco: does "log of operations" mean a sequential log? If yes, then one can use any old hash function, combined with its "midstate". This doesn't tell you how the midstate was arrived at, however.
murch has quit [Quit: Leaving.]
<nicolagreco>
amiller: (hi!) where can I read more about cut-and-choose?
asynk has quit [Read error: Connection reset by peer]
<bsm1175321>
One can also use a single Merkle tree, where the hash state is a path to the most recently added element, which includes the Merkle root, and enough information to update the Merkle root by adding one element. This allows one to retain Merkle proofs about any other elements that were added prior to the most recent update.
asynk has joined #bitcoin-wizards
<amiller>
nicolagreco, here's a nice paper explaining how cut-and-choose works in the setting of multi-party computation
<bsm1175321>
nicolagreco: A related idea is "incremental hash functions" (google for more) https://eprint.iacr.org/2015/1028.pdf but after fooling with this paper for a while, I came to the conclusion that all their constructions are log(n) in the number of stored elements, and a Merkle tree (as described above) is simpler and has the same asymptotic scaling.
Emcy has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 252 seconds]
moli has quit [Ping timeout: 240 seconds]
proslogion has quit [Ping timeout: 260 seconds]
belcher has quit [Quit: Leaving]
xissburg has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
<maaku>
incremental hash functions provide a different engineering tradeoff
<maaku>
as the size of the structure increases you tradeoff accuracy for constant-size state
mdavid613 has quit [Quit: Leaving.]
rusty2 has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
btcdrak has quit [Quit: Connection closed for inactivity]
rusty2 is now known as rusty
yorick_ has joined #bitcoin-wizards
yorick has quit [Ping timeout: 250 seconds]
pro has quit [Quit: Leaving]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
<bsm1175321>
maaku: I think there's a very deep misunderstanding driven by Bloom filters. What anyone actually cares about is false-positives. Once you fix that, you end up with logarithmic scaling. The additional parameter introduced is just confusing.
<bsm1175321>
constant size is only possible by increasing the false-positive rate...
<gmaxwell>
the functions maaku is talking about do not have false positives, or admit efficient membership tests.
<gmaxwell>
(no false positives except in the cryptographic sense, which I assume you mean too when you say log scaling)
<gmaxwell>
They support efficient add and removal of members.
<gmaxwell>
e.g. useful for keeping a hash of your whole database, while you insert/remove/update records.
<gmaxwell>
and they have constant size state (state size depends on security, not number of elements)
<gmaxwell>
the 'dumb' and very very insecure simple version of those datastructure is a hash over items where the hash is the result of H(index_0||itemdata_0) ^ H(index_1||itemdata_1) ...
TomMc has quit [Ping timeout: 244 seconds]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
TomMc has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
cyphase has quit [Ping timeout: 244 seconds]
cyphase has joined #bitcoin-wizards
polyclef_ has quit [Ping timeout: 244 seconds]
TomMc has quit [Ping timeout: 250 seconds]
ThomasV has joined #bitcoin-wizards
zooko has joined #bitcoin-wizards
zooko has quit [Client Quit]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
ThomasV has quit [Ping timeout: 244 seconds]
Alopex has joined #bitcoin-wizards
Transisto2 has quit [Read error: Connection reset by peer]
Transisto2 has joined #bitcoin-wizards
polyclef_ has joined #bitcoin-wizards
shesek has quit [Ping timeout: 264 seconds]
btcdrak has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
jannes has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
bitjedi has quit [Ping timeout: 244 seconds]
bitjedi has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
rubensayshi has joined #bitcoin-wizards
rusty has quit [Ping timeout: 240 seconds]
JackH_ has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
ithicad has quit [Ping timeout: 264 seconds]
laurentmt has joined #bitcoin-wizards
markus-k has joined #bitcoin-wizards
paveljanik has quit [Quit: Leaving]
laurentmt1 has joined #bitcoin-wizards
andytoshi has quit [Ping timeout: 265 seconds]
laurentmt has quit [Ping timeout: 265 seconds]
laurentmt1 is now known as laurentmt
proslogion has joined #bitcoin-wizards
murch has joined #bitcoin-wizards
hashtagg_ has joined #bitcoin-wizards
hashtag_ has quit [Ping timeout: 258 seconds]
Ylbam has joined #bitcoin-wizards
hashtag_ has joined #bitcoin-wizards
hashtagg_ has quit [Ping timeout: 244 seconds]
andytoshi has joined #bitcoin-wizards
ithicad has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 264 seconds]
pro has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
mkarrer has quit [Remote host closed the connection]
mkarrer has joined #bitcoin-wizards
licnep has joined #bitcoin-wizards
r0ach has quit []
Emcy has joined #bitcoin-wizards
JackH_ has quit [Quit: Leaving]
Mazz_ has quit [Read error: Connection reset by peer]
ThomasV has quit [Ping timeout: 260 seconds]
jouke has quit [Changing host]
jouke has joined #bitcoin-wizards
cyphase has quit [Ping timeout: 258 seconds]
Mazz_ has joined #bitcoin-wizards
cyphase has joined #bitcoin-wizards
InsidiousPoet has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
Chris_Stewart_5 has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
TomMc has joined #bitcoin-wizards
instagibbs has quit [Ping timeout: 240 seconds]
rustyn has quit []
instagibbs has joined #bitcoin-wizards
licnep has quit [Quit: Connection closed for inactivity]
Guyver2 has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
aalex_ has quit [Ping timeout: 244 seconds]
Samdney has joined #bitcoin-wizards
shesek has quit [Ping timeout: 244 seconds]
laurentmt has quit [Quit: laurentmt]
shesek has joined #bitcoin-wizards
aalex has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 260 seconds]
Ylbam has quit [Quit: Connection closed for inactivity]
Chris_Stewart_5 has quit [Ping timeout: 250 seconds]
<Taek>
kanzure: 404
lvns_ has joined #bitcoin-wizards
lvns has quit [Ping timeout: 265 seconds]
buZz is now known as buzz_
buzz_ is now known as buzz__
buzz__ is now known as buZz
NewLiberty has quit [Ping timeout: 258 seconds]
ThomasV has quit [Ping timeout: 240 seconds]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
ryan`c is now known as ryan-c
ryan-c is now known as ryan`c
koshii has quit [Ping timeout: 265 seconds]
ryan`c is now known as ryan-c
koshii has joined #bitcoin-wizards
mdavid613 has joined #bitcoin-wizards
zooko has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 265 seconds]
oleganza has joined #bitcoin-wizards
jannes has quit [Quit: Leaving]
zooko` has joined #bitcoin-wizards
zooko has quit [Ping timeout: 250 seconds]
oleganza has quit [Quit: oleganza]
NewLiberty has joined #bitcoin-wizards
BashCo_ has quit [Remote host closed the connection]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
rubensayshi has quit [Remote host closed the connection]
adiabat has joined #bitcoin-wizards
<maaku>
bsm1175321: as gmaxwell briefly mentioned the driving reason for incremental hash functions is hashes of database or file system state
<maaku>
the lack of an efficient membership query makes them somewhat incidental to this purpose :\
<maaku>
I do think a monotone version control system with incremental hashes for tree/manifest state and script signatures would be VERY cool though
Yogh has quit [Ping timeout: 244 seconds]
BashCo has joined #bitcoin-wizards
Yogh has joined #bitcoin-wizards
NewLiberty_ has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 240 seconds]
zooko` has quit [Remote host closed the connection]
zooko` has joined #bitcoin-wizards
Sosumi has quit [Ping timeout: 244 seconds]
zooko` has quit [Remote host closed the connection]
zooko` has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
aalex_ has joined #bitcoin-wizards
aalex has quit [Ping timeout: 264 seconds]
TomMc has quit [Ping timeout: 265 seconds]
mdavid613 has quit [Quit: Leaving.]
TomMc has joined #bitcoin-wizards
oleganza has joined #bitcoin-wizards
mdavid613 has joined #bitcoin-wizards
alee2 has joined #bitcoin-wizards
alee2 is now known as valencia
oleganza has quit [Client Quit]
oleganza has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
NewLiberty_ has quit [Ping timeout: 240 seconds]
Guest10 has joined #bitcoin-wizards
Guest10 has quit [Client Quit]
zooko` has quit [Remote host closed the connection]
NewLiberty has quit [Ping timeout: 260 seconds]
NewLiberty has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
Oizopower has joined #bitcoin-wizards
oleganza has quit [Quit: oleganza]
paveljanik has joined #bitcoin-wizards
oleganza has joined #bitcoin-wizards
jcorgan has quit [Quit: leaving]
MoALTz has quit [Quit: Leaving]
aalex has joined #bitcoin-wizards
aalex__ has joined #bitcoin-wizards
aalex_ has quit [Ping timeout: 265 seconds]
aalex has quit [Ping timeout: 260 seconds]
ThomasV has joined #bitcoin-wizards
Guyver2 has quit [Ping timeout: 252 seconds]
Guyver2 has joined #bitcoin-wizards
rusty2 has joined #bitcoin-wizards
Guyver2 has quit [Remote host closed the connection]
NewLiberty has quit [Ping timeout: 244 seconds]
belcher has joined #bitcoin-wizards
<kanzure>
welp, i forgot the problems with my "push validation to p2p payments where one of send/receive wont work without full validation, as an opt-in consensus rule" concept. at minimum there was a problem with how it could be outsourced, even if you tie private keys into the scheme somehow (although users seem to reasonably understand the concept of securing their own private keys, more than they seem to understand the benefits of running ...
<kanzure>
... their own fully-validating node)
<kanzure>
with probabilistic partial checking/validation of data, perhaps the scheme would be trivial enough that outsourcing wouldn't be as much of a problem?
Oizopower has quit [Quit: Connection closed for inactivity]
rusty21 has joined #bitcoin-wizards
rusty2 has quit [Ping timeout: 276 seconds]
waxwing has quit [Quit: Leaving]
waxwing has joined #bitcoin-wizards
jl2012 has quit [Quit: Connection closed for inactivity]
ThomasV has quit [Ping timeout: 240 seconds]
ThomasV has joined #bitcoin-wizards
proslogion has quit [Ping timeout: 244 seconds]
rusty21 has quit [Ping timeout: 252 seconds]
aalex__ is now known as aalex
Meeh has quit [Quit: No Ping reply in 180 seconds.]
Meeh has joined #bitcoin-wizards
TomMc has quit [Ping timeout: 240 seconds]
Meeh has quit [Ping timeout: 244 seconds]
Meeh has joined #bitcoin-wizards
oleganza has quit [Quit: oleganza]
ThomasV has quit [Ping timeout: 244 seconds]
InsidiousPoet has quit [Quit: ||]
grubles has quit [Remote host closed the connection]