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
Belkaar has quit [Ping timeout: 255 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Chris_St1 has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
Chris_St1 has quit [Ping timeout: 240 seconds]
Chris_St1 has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
tromp has joined #bitcoin-wizards
dabura667 has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
Giszmo has joined #bitcoin-wizards
Chris_St1 has quit [Ping timeout: 248 seconds]
rusty has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 248 seconds]
Dyaheon has joined #bitcoin-wizards
Aranjedeath has joined #bitcoin-wizards
pro has quit [Quit: Leaving]
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 260 seconds]
Aaronvan_ has quit []
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
Chris_St1 has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
sipa has quit [Changing host]
sipa has joined #bitcoin-wizards
Chris_St1 has quit [Ping timeout: 240 seconds]
Giszmo has quit [Quit: Leaving.]
rusty has quit [Ping timeout: 240 seconds]
Dizzle has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 255 seconds]
<maaku>
sipa: I have confirmed experimentally (by implementing both) that the cute 3-bit-per-inner-node serialization and the verifier's perspective relative-offset-of-each-hash result in exactly the same proof lengths, down to the bit
<maaku>
both are subject to some optimizations if you drop requirements such the proof being self-segmenting
<sipa>
maaku: hmm, the same number of bits?
<sipa>
my belief was that the 3-bit-per-inner-node approach is 2 bits less
<maaku>
it is precisely 2 bits less. but I need those two bits to encode the 0-element tree, and the two versions of the 1-element tree (skip hash or include)
<sipa>
right
<sipa>
but under the assumption that any explored tree has at least 1 relevant element, that is not needed :)
<sipa>
(because the only case with no inner nodes corresponds to the situation where the root is an element)
<sipa>
would you like me to do a write-up on the 3-bit inner node idea, or are you working on one?
<maaku>
I've eeked out a bit more compression from the verifier's perspective by dropping the self-segminting requirement, prefixing the max height, etc. But it's really just a few bits less (~height of tree). i imagine analogous optimizations exist for the 3-bit encoding
<maaku>
sipa: I have ideas for one (beyond the naive one I already implemented). I conceptually like the verifier's perspective on the principle that proofs should be optimally simple to verify.
<sipa>
i can write a logspace verifier for the 3-bit structure
<maaku>
But the fixed width of the 3-bit code lends itself to a fast table implementation with no bit fidling, and merging or splitting proofs is as simple as splicing in the right locations.
<maaku>
So I think I'm going to stop micro-optimizing and just go with that, 3-bit code with no extra optimizations.
<maaku>
Storing the max height lets you drop to half the bits on the bottom nodes of the tree, great for balanced trees. But this mucks with fast table decodes, and considering we're only saving <<1.5 bits per 512 bits of hashes ... kinda not worth it
<maaku>
sipa: I'll take a stab at it. A log-space, single pass implementation seems pretty straight forward
<sipa>
cool
<maaku>
Actually something I could use advice with, if you have any is which codepoints to assign to which node configurations. If chosen wisely, string sorting by binary representation could accomplish something useful
<maaku>
I don't know what 'useful' is. What does it mean to relationally compare two Merkle inclusion proofs?
<sipa>
i would say, innernode=0, relevant element=1, hash=2
<sipa>
and then encode left_style*3 + right_style
<sipa>
very easy to decode
rmwb has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
rmwb has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
<sipa>
(and as left_style and right_style can't be both 'hash', 8 is impossible)
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
wizkid057 has quit [Read error: Connection reset by peer]
tromp has quit [Ping timeout: 255 seconds]
TheSeven has quit [Ping timeout: 246 seconds]
TheSeven has joined #bitcoin-wizards
<maaku>
For sure. That's what I did in may naive implementation. I guess I'm wondering if there are algorithmic reasons you might sort a container of trees, where the ordering is meaningful.
<maaku>
And if so, what those requirements are. (why should a inner node sort before a hash, and why the inclusion before the skipped hash?)
<maaku>
Other than that making decoding simple since code=8 is impossible
wizkid057 has joined #bitcoin-wizards
<sipa>
well is there.even a meaningful ordering for proofs with a real-world use?
<maaku>
Well I think that's my question :P
<sipa>
okay, right
<sipa>
i guess my answer is no, then
anon616 has left #bitcoin-wizards [#bitcoin-wizards]
anon616 has joined #bitcoin-wizards
TheSeven has quit [Ping timeout: 246 seconds]
TheSeven has joined #bitcoin-wizards
<maaku>
An ordering, any ordering is useful, just to support std::set, obviously.
<maaku>
And if you further require the items to be ordered left-to-right in the fully expanded tree, then switching to (DESCEND, SKIP, INCLUDE) would mean that lexigraphical comparison of proof strings would be equivalent to lexigraphical comparison of the list of elements extracted against those of other subtrees
<maaku>
That's the best I've come up with
<maaku>
That would make SKIP,SKIP = 5 though, but that can be worked around
coinsmurf has joined #bitcoin-wizards
packetsmurf has quit [Ping timeout: 240 seconds]
<sipa>
still easy to decode
<sipa>
left = (code - (code > 4)) / 3
<sipa>
right = (code - (code > 4)) % 3
<sipa>
or a table
Aranjedeath has quit [Quit: Three sheets to the wind]
rusty1 has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 240 seconds]
rmwb has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
<sipa>
or some branches: if (code < 5) { if (code < 3) left=DESCEND; else left=SKIP; } else { left=INCLUDE; }
Dizzle has quit [Remote host closed the connection]
Dizzle has joined #bitcoin-wizards
rusty1 has quit [Ping timeout: 260 seconds]
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 240 seconds]
tromp has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
rmwb_ has joined #bitcoin-wizards
DrOlmer has quit [Ping timeout: 240 seconds]
rmwb has quit [Ping timeout: 255 seconds]
DrOlmer has joined #bitcoin-wizards
rmwb_ has quit [Remote host closed the connection]
BashCo has quit [Remote host closed the connection]
chjj has quit [Ping timeout: 255 seconds]
<maaku>
sipa: Oh I'm going to try to do the whole thing as a table, reading a byte at a time
<maaku>
Three tables actually, since alignment with the start of a byte repeats every 24 bits
<sipa>
maaku: that seems orthogonal
<sipa>
you can read a byte at a time, but still interpret the values using arithmetic
go1111111 has quit [Remote host closed the connection]
intcat has quit [*.net *.split]
arubi has quit [*.net *.split]
BashCo has joined #bitcoin-wizards
intcat has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
CheckDavid has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
dnaleor has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
dnaleor has quit [Quit: Leaving]
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 248 seconds]
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 240 seconds]
execute has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
tromp has joined #bitcoin-wizards
JackH has quit [Ping timeout: 255 seconds]
daszorz has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 260 seconds]
tromp has quit [Remote host closed the connection]
<maaku>
sipa: well I mean with a lookup table it will all be pre-decoded
Newyorkadam has joined #bitcoin-wizards
<maaku>
Eight nodes straddled across three bytes as follows [000 111 22] [2 333 444 5] [55 666 777]
<maaku>
Three different 256 element lookup tables, where the LUT provides the pre-decoded information for the two nodes and the 1 or 2 residuals for the split nodes. A further 3, 8-element LUTs provide the residual->node mappings
<maaku>
fully and wastefully expanded with the styles, residuals, etc. occupying one byte each, that totals about 4k, which fits in L1 cache
Dizzle has quit [Quit: Leaving...]
rmwb has joined #bitcoin-wizards
<maaku>
And by rough estimation of probabilities you'd have hit half the cache lines in proofs larger than 16 inner nodes
<maaku>
Which is a little large actually, so I may be prematurely optimizing or want to consider a smaller LUT
meshcollider has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 255 seconds]
Newyorkadam has quit [Quit: Newyorkadam]
dabura667 has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 248 seconds]
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
Emcy has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 255 seconds]
tromp has joined #bitcoin-wizards
jannes has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
Chris_St1 has joined #bitcoin-wizards
wallet42 has quit [Read error: Connection reset by peer]
wallet42 has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
thrmo has joined #bitcoin-wizards
thrmo is now known as sellb42l8
Chris_St1 has quit [Quit: WeeChat 1.4]
rmwb has quit [Ping timeout: 258 seconds]
sellb42l8 is now known as thrmo
Chris_Stewart_5 has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 264 seconds]
dnaleor has quit [Ping timeout: 255 seconds]
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
Aaronvan_ is now known as AaronvanW
laurentmt has quit [Quit: laurentmt]
Giszmo has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 246 seconds]
Newyorkadam has joined #bitcoin-wizards
Emcy has quit [Read error: Connection reset by peer]
rmwb has joined #bitcoin-wizards
DrOlmer has quit [Ping timeout: 248 seconds]
DrOlmer has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 248 seconds]
rmwb has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 260 seconds]
dnaleor has quit [Read error: Connection reset by peer]
Chris_Stewart_5 has quit [Quit: WeeChat 1.4]
adiabat has quit [Quit: WeeChat 1.4]
rmwb has joined #bitcoin-wizards
<waxwing>
anyone know where i can see the latest proposed version of schnorr sig. agg. (with the delinearization bit)? thanks
<waxwing>
andytoshi, thanks. it's probably only tangential, but i suddenly realised that if i wanted to write out your atomic swap scriptless script setup i have to consider how the schnorr 2 of 2 is written out.
<waxwing>
i guess for the purposes of just rough outline, the "basic" setup where you just pass over nonce points and pubkeys is OK.
<andytoshi>
yeah. can you add signatures with those points of themselves to the protocol?
<andytoshi>
like when you pass R also pass a signature with R of R
<andytoshi>
this will prevent related-key attacks without requiring delinearization (for _that_ we have a paper that was just submitted, so hopefully we'll have a solution to point to in coming months)
JackH has quit [Ping timeout: 240 seconds]
jb55 has joined #bitcoin-wizards
wraithm has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 255 seconds]
JackH has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 246 seconds]
jb55 has quit [Ping timeout: 255 seconds]
BashCo has quit [Remote host closed the connection]
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
Aaronvan_ is now known as AaronvanW
Noldorin has joined #bitcoin-wizards
Newyorkadam has quit [Quit: Newyorkadam]
dnaleor has joined #bitcoin-wizards
<waxwing>
andytoshi, ok thanks, will come back to that, something else: do i take it that it's a given that you have a timeout branch in the outpoint Alice/Bob pay in to (a la the basic atomic swap)? so like one branch is CHECKSCHNORRSIG (w/e) for the 2/2 pubkey and one branch for a CLTV + Alice, type of thing.
<andytoshi>
waxwing: yeah
<andytoshi>
for swaps you can just use normal locktime transactions though rather than CLTV
<andytoshi>
which saves a little space and privacy
<waxwing>
oh that's a point .. we want privacy here so .. we don't even want locktimes come to that, don't you think?
rmwb has joined #bitcoin-wizards
<waxwing>
well that's another point, of course the huge win is no publishing a secret that connects, so even if there's a locktime it's still worth it
<andytoshi>
well the locktimed transactions ideally never get published
<andytoshi>
oh, derp
<andytoshi>
no ... counterderp. the locktimed transactions ideally never get published
<waxwing>
yes i think you can do the "CoinSwap" style that doesn't publish the backouts
<andytoshi>
you don't even need to do the coinswap thing, which avoids publishing the hash-preimage challenges
<andytoshi>
because there are no hash challenges to begin with
<waxwing>
right .. but if there's a second timelock branch? or if there's just a locktime on the transaction?
<waxwing>
ok i can see your argument, if it's just, the fact that it has a locktime isn't nearly that bad.
<waxwing>
no hang on i haven't got this right at all lol
<andytoshi>
there's no second timelock branch. the timelocks are only for refunds in case somebody backs out
<waxwing>
right. exchange backouts in advance. got it.
<andytoshi>
yep
BashCo has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 255 seconds]
daszorz has quit [Read error: Connection reset by peer]
thrmo has quit [Quit: Waiting for .007]
pro has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
jb55 has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 246 seconds]
Ylbam has joined #bitcoin-wizards
abpa has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
rmwb has quit [Ping timeout: 255 seconds]
jtimon has quit [Remote host closed the connection]
laurentmt has quit [Quit: laurentmt]
tromp has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
arubi has quit [Remote host closed the connection]
meshcollider has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 258 seconds]
daszorz has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 258 seconds]
Emcy has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
intcat has quit [Ping timeout: 248 seconds]
intcat has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
Emcy has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
<waxwing>
i'll probably make a diagram, but, tomorrow
rusty has quit [Ping timeout: 248 seconds]
<arubi>
will probably try to run this in bc, but also tomorrow :)
chjj has quit [Ping timeout: 240 seconds]
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 260 seconds]
rmwb has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
rmwb has quit [Ping timeout: 255 seconds]
daszorz has quit [Read error: Connection reset by peer]
anon616 has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
anon616 has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 246 seconds]
<waxwing>
arubi, updated it a fair bit after andytoshi helped me understand the right way to handle the 'related key' thing. same basic proto. but different way of constructing the keys for multisig.
* waxwing
has no problem taking arubi seriously anymore when he says i'll just go ahead and write that in bc ...
<andytoshi>
lol, ditto
meshcollider has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
DrOlmer has quit [Ping timeout: 255 seconds]
DrOlmer has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 264 seconds]
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
rmwb has joined #bitcoin-wizards
v20100 has joined #bitcoin-wizards
AaronvanW has quit [Read error: Connection reset by peer]
tromp has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
wraithm has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
vicenteH has quit [Ping timeout: 248 seconds]
v20100 has quit [Ping timeout: 255 seconds]
Terr has quit [Ping timeout: 255 seconds]
LeMiner has quit [Read error: Connection reset by peer]
rusty has joined #bitcoin-wizards
pro has quit [Quit: Leaving]
tromp has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
tromp has quit [Remote host closed the connection]