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
Giszmo has quit [Ping timeout: 240 seconds]
DrOlmer has quit [Ping timeout: 260 seconds]
DrOlmer has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 255 seconds]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
dnaleor has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 255 seconds]
Giszmo has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Belkaar has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
Ylbam has quit [Quit: Connection closed for inactivity]
airbreather has joined #bitcoin-wizards
airbreather_ has quit [Ping timeout: 258 seconds]
danrobinson has quit [Quit: danrobinson]
Chris_Stewart_5 has quit [Ping timeout: 255 seconds]
luke-jr has joined #bitcoin-wizards
jb55 has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 248 seconds]
meshcollider has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 258 seconds]
jb55 has joined #bitcoin-wizards
<maaku>
I have a CS theory question for this group. A Huffman code is optimal if the probabilities are known and fixed. However is there a method for constructing trees that try to minimize the path for accessing multiple elements?
<maaku>
Obviously the frequency of each A,B pairing (for accessing 2 items) or A,B,C (3, etc.) would be given.
<maaku>
And by "minimize path" I mean that shared path prefixes are not double-( or triple-)counted
<kanzure>
if you allow for stepwise increase in path length cost, your method could be just put the frequently-accessed stuff at the top of the tree, then for double cost the less popular stuff at the next level, and so on.
<kanzure>
(assuming binary tree)
<kanzure>
H(root) -> (H(tree(H(tree(...)), H(C)), H(B)), H(A)) so H(A) is cheapest to lookup, B is more expensive, C is even more expensive.
<sipa>
maaku: what do you mean with 'multiple elements' ?
<gmaxwell>
maaku: huffman tress also require that the probablities are all 1/2^n for optimality. (though not your question) ... I know how to construct ones that have a depth limit, which seems relevant to your interests.
<sipa>
maaku: oh, i see what you're asking
<gmaxwell>
I think this shared prefix property might also just be obeyed by huffman codes, if you assume that the probablities are independant.
<maaku>
gmaxwell: is there anything better than Huffman codes for non-binary probabilities?
<gmaxwell>
absolutely, but nothing that maps into a binary decision tree, which is what I assume you want. (because I assume you're using this for hashtree layouts)
<maaku>
gmaxwell: yes, and yes. with those restrictions I think Huffman is optimal, but would like to be corrected if wrong
<maaku>
kanzure: that's what I'm trying to do. my question is more, "for given probability distributions, what's the optimal tree shape?"
<maaku>
gmaxwell: constructing with a depth limit would be interesting. not what I'm working on right now, but I'd be good to know how to do that
<kanzure>
uhrm for the tree sizes you are considering, is it practical to just run some quick iterative emperical method to figure that out? and then you cna look at the results to answer your question (or if it's fast enough, just include that in your implementation anyway).
<maaku>
Specifically I'm trying to find tree shapes that I should be benchmarking serialization choices against. "Maximally-unbalanced (a list) at the top, then a fully-balanced tree at the bottom" is a good intuition for what this *should* look like, based on real world use cases
<maaku>
Oh, and here's a practical justification: key tree threshold signatures where 'individual' signers use their own internal thresholds. for example, a 4-way script has an 'everybody signs' top-level conditional that must actually be the combinatorial possibilities of each individual signer
<maaku>
and in many cases each actor would specify their own probability distribution for their sub-key combinations. e.g. if it is 2-of-3 there is 84% confidence one set of 2 keys will be used, 15% confidence the other set, and 1% for the worst-case paper key recovery
<maaku>
that could easily chop up high level reasoning about what the tree structure "should" be, and at some point it becomes better to add probability semantics to the key-tree-like signing condition language and have it auto-generate tree structures via a standard method
go1111111 has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
Giszmo has quit [Read error: Connection reset by peer]
TheSeven has quit [Ping timeout: 255 seconds]
TheSeven has joined #bitcoin-wizards
Giszmo has joined #bitcoin-wizards
intcat has quit [Ping timeout: 248 seconds]
intcat has joined #bitcoin-wizards
TheSeven has quit [Ping timeout: 258 seconds]
[7] has joined #bitcoin-wizards
Emcy_ has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
Emcy has quit [Read error: Connection reset by peer]
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
chjj has quit [Ping timeout: 248 seconds]
meshcollider has quit [Quit: Connection closed for inactivity]
priidu has joined #bitcoin-wizards
sdfgsdfg has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 248 seconds]
Emcy has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
sdfgsdfg has quit [Ping timeout: 240 seconds]
Emcy has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
davec has quit [Ping timeout: 260 seconds]
Emcy has quit [Ping timeout: 255 seconds]
dnaleor has joined #bitcoin-wizards
davec has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
priidu has quit [Remote host closed the connection]
Emcy_ has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
meshcollider has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
Emcy_ has joined #bitcoin-wizards
gotanyideas has joined #bitcoin-wizards
DrOlmer has quit [Ping timeout: 248 seconds]
DrOlmer has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 240 seconds]
Alina-malina has joined #bitcoin-wizards
Terr has quit [Ping timeout: 240 seconds]
Terr has joined #bitcoin-wizards
deusexbeer has quit [Ping timeout: 240 seconds]
deusexbeer has joined #bitcoin-wizards
daszorz has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 240 seconds]
gotanyideas has joined #bitcoin-wizards
null_radix has quit [Remote host closed the connection]
Pilfers has quit [Remote host closed the connection]
intcat has quit [Remote host closed the connection]
intcat has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
daszorz2 has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
alt0id has quit [Ping timeout: 240 seconds]
DrOlmer has quit [Remote host closed the connection]
<maaku>
sipa: Interesting tidbit that probably has a theoretical explanation : if you enumerate the number of possible proofs (tree structure plus has inclusion bit) for k-of-n, for all n between 1 and max is equal to 2^(max+1) - 1
<maaku>
so all k-of-n for 0<=k<=n and 0<=n<=7 hass 255 possible resulting trees / proof bits if you simply enumerate them
<maaku>
damnit that was too good of a result to be true. why do I always find an error right after announcing something?
<maaku>
I was double-counting a few trees, so it's actually a little bit less, I'll have to see if there's a pattern to these numbers
danrobinson has joined #bitcoin-wizards
jbase has joined #bitcoin-wizards
danrobinson has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 264 seconds]
Anduck has quit [Ping timeout: 240 seconds]
Alina-malina has joined #bitcoin-wizards
Anduck has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 260 seconds]
Alina-malina has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 255 seconds]
Alina-malina has joined #bitcoin-wizards
eck has quit [Quit: we out here]
eck has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
meshcollider has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 240 seconds]
Alina-malina has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 240 seconds]
Alina-malina has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 240 seconds]
jtimon has joined #bitcoin-wizards
Alina-malina has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 240 seconds]
Alina-malina has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
anon616 has quit [Remote host closed the connection]
jb55 has joined #bitcoin-wizards
Noldorin has quit [Remote host closed the connection]
kenobi has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
anon616 has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 240 seconds]
AaronvanW has quit [Ping timeout: 258 seconds]
Alina-malina has joined #bitcoin-wizards
c0rw1n_ has quit [Ping timeout: 258 seconds]
anon616 has quit [Remote host closed the connection]