--- Log opened Sun Mar 10 00:00:47 2013
03:03 <@gmaxwell> On the subject of Moon-rocket P2SH,  a proposed solution to uneconomical to spend utxo is this thing I just put on my alt_ideas page (inspired by some talk in #bitcoin-dev):
03:04 <@gmaxwell> * Transaction cost prepayment: One problem is that it's possible to create UTXO that are unprofitable to redeem.
03:04 <@gmaxwell> ** Instead make every output specify a max_size, which is the maximum marginal increase in size from redeem this txout in a new transaction.
03:04 <@gmaxwell> ** max_size serialized as an unsigned variable length int minus whatever the smallest credible max_size is, (e.g. something like 40 for bitcoin)
03:04 <@gmaxwell> *** This makes sure people aren't incentive to write unspendable txn, perhaps a larger minimum max_size should be used, e.g. the size of the smallest secure TX_IN.
03:04 <@gmaxwell> ** Then for the 'cost' of a transaction use  cost = MAX(size-sum_inputs(max_size),minimum_viable_txn_size) +  sum_outputs(max_size)
03:04 <@gmaxwell> ** In order to economical align cost the blocksize limit should be based on it rather than size.
07:37 <@gmaxwell> lol https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas#Coin_of_the_moonmen
08:58 <@gmaxwell> oh amiller
08:59 <@gmaxwell> amiller: Get this. POW = H(header || nonce || H(utxo_lookup(nonce))).   With this pow: Validation _is_ mining.
08:59 <@gmaxwell> if you have utxo lookups to perform, you are mining in the process. If you've run out of lookups to perform you just do ones at random.
10:28 < HM> hmm interest gmaxwell
10:29 < HM> gmaxwell: the problem i see with that is the hash rate will be abysmal
10:29 < HM> gmaxwell: perhaps 2 nonces with some mathematical relationship, so miners only have to do the lookup one in every X nonces
10:31 < petertodd> HM: the absolute rate of a PoW function is irrelevant
10:33 < HM> true, but once you have db i/o in there it's no longer a function of raw computation
10:33 < HM> keeping it dominated by one type of bottleneck is ideal
10:34 < HM> if it was 50% i/o and 50% computation then you have a more volatile rate
10:35 < HM> or perhaps not, but it complicates things
10:41 < petertodd> db io is just a type of computation
10:44 < HM> bah
10:44 < HM> all i'm saying is a pure number crunching like a hash doesn't depend on the i/o capabilities of the host.
10:45 < HM> your scheme renders avalon boxes useless for instance because the utxo queries will dominate
10:45 < HM> that's not necessarily bad, i would just suggest reducing the ratio of 1:1 hash:utxoquery
10:46 < HM> on the other hand maybe higher i/o keeps ordinary people in the game longer
10:50 < petertodd> it's meant to be an alt-chain, not an extension to bitcoin
10:50 < petertodd> and it's gmaxwell's scheme
10:53 < HM> indeed
10:54 < HM> I think memory hardness is the way forward
13:09 <@gmaxwell> odd that hm doesn't realize that I'm describing a memory hard pow.  Should I have called it TrendyPow(tm) instead? :P
13:16 < jgarzik> RE decentralized network and micropayments:  given a network, how to compensate each node, in miniscule micropayment amounts, for work they perform relaying?
13:16 < jgarzik> i.e. the old how-to-prove-you-did-work problem
13:18 < jgarzik> I guess you could ask the same question about bitcoin:  presuming the existence of an off-chain microtransaction system, could there be some provable compensation method for people who simply run full nodes?
13:18 < jgarzik> You can test and sample, I suppose
13:35 <@sipa> 110us for a*P+b*G; 12us for key decompression; 26us for the scalar inverse in ECDSA (@&$*# slow OpenSSL); 11us for converting X to affine coords
13:35 <@sipa> total: ~160us for a full signature validation
13:36 < jgarzik_> Heh, maybe we can drop openssl dep soon
13:36 <@sipa> which means around 500k cycles, or only 2x as much as Ed25519
13:37 <@sipa> the same thing in naive OpenSSL is around 600us
13:37 < jgarzik_> How much validation code can be reued by signing code, if any, I wonder
13:37 < jgarzik_> *reused
13:37 <@sipa> most
13:38 <@sipa> signing is just a lot simpler
13:38 <@sipa> but for signing you actually want other algorithm, which don't leak key information via timing
13:39 <@sipa> that 26us for the scalar inverse should be doable in 3us or so, i have no clue why OpenSSL is so slow at that (it's the few parts of my code that still rely on OpenSSL, but it can easily be changed to GMP or so)
13:57 < HM> good work sipa
13:57 < HM> jgarzik_: dropping openssl is unlikely, you'll need something for SSL/TLS
13:58 < jgarzik_> Not for all apps / libs :-)
13:59 < HM> true
14:02 < jgarzik> Android IRC client is not too bad
14:04 < HM> Yaaic?
14:05 < HM> sipa: your numbers make me feel better about this rpc implementation i'm testing
14:05 <@sipa> HM: i'd be very glad to drop SSL/TLS and tell people to use stunnel if they really want to expose an RPC port to an untrusted network
14:05 < HM> 30,000 synchronous calls over localhost tcp / second
14:06 < HM> so 34us, won't be a bottleneck
14:06 < HM> the EC stuff sounds like it'll dominate
15:56 <@sipa> swap OpenSSL for GMP: down to 136us
15:56 <@sipa> (though haven't validated whether the results are correct)
16:36 < HM> nice
16:39 < HM> sipa: did you optimise exponentiation yet?
16:40 <@sipa> sure
16:43 <@sipa> there are not many optimizations left that i know about
16:48 < HM> Still, a four fold performance increase over current bitcoind?
16:49 <@sipa> something like that
16:49 < HM> that's sweet
16:59 <@sipa> the worst part: creating bug-for-bug identical signature decoder
17:06 < HM> well you can be lazy and leave out the bugs
17:06 < HM> I'll forgive you
17:07 <@gmaxwell> No, we won't. Not matching the bugs would be a bug.
17:07 <@sipa> not matching the bugs means a potentially forking client
17:08 <@sipa> though i'm well aware of which violations of DER-encoding for signatures appear on the network, and matching those isn't hard, i can't know what else OpenSSL might accept
17:08 <@sipa> trivial solution: use OpenSSL to do the signature decoding :)
17:27 < nanotube> what if openssl decides to fix the bugs at some point?
17:27 <@gmaxwell> nanotube: bitcoin is over.
17:27 <@gmaxwell> :P
17:28 < nanotube> heh
17:28 <@gmaxwell> this is one of the reason that having external libraries define our normative blockchain behavior is surprisingly risky. Most other software doesn't have the suicide pact for bug preservation we do. :P
17:29 < nanotube> indeed
17:29 <@gmaxwell> In my eyes the whole of the blockchain code would be some hermetically sealed single set of C files which don't even call any libc functions, beyond those needed to allocate memory and use the disk. :P
17:30 <@sipa> nanotube: it's not bugs as such: they accept ill-formatted signatures; in many settings, that is wanted behaviour
17:30 <@sipa> the problem is that it implicitly defines a hard network rule for us
17:30 < HM> gmaxwell: *C++ files :P
17:30 <@gmaxwell> The old and now increasingly depricated internet "be forgiving in what you accept"
17:31 <@gmaxwell> HM: If C++, it would really properly be a subset. it shouldn't use STL containers. Their _exact_ visible behavior is not defined.
17:31 <@gmaxwell> (or at least it would have to be very careful in how they were used)
17:32 <@gmaxwell> Basically it can't use implementation defined behavior. In C I know how to do this, I'm sure it's possible in C++ but I don't personally know how.
17:32 < HM> the STL containers let you use custom allocators
17:33 < HM> i'm not sure what in particular you're worried about
17:34 <@sipa> gmaxwell: you could copy the STL headers into the project if you're really worried :)
17:34 <@sipa> they're not system dependent
17:34 <@gmaxwell> sipa: good luck getting them to compile with any random compiler! :P
17:35 <@sipa> gmaxwell: obviously you copy g++'s source code into the project as well :p
17:35 <@sipa> and the linux source code
17:35 <@sipa> and the design docs of your CPU.... oh wait
17:35 < HM> SeaBIOS for open bios
17:35 < HM> then run the whole thing in a virtual machine
17:35 <@gmaxwell> But yea, there you go— limitations on my C++ clue. I'm sure there are ways to avoid implementation defined behavior (avoiding implementation bugs perhaps tricker— in C the compilers are now tested against random ASTs for agreement among implementations, including implementations like CompCert)
17:36 <@gmaxwell> sipa: if the compiler isn't buggy then your exposure is just malloc and disk io not working.
17:36 < HM> malloc isn't reliable
17:36 <@gmaxwell> But there is a _big_ difference between bug and implementation defined behavior.
17:36 < HM> Linux will happily allocate more memory than you have
17:36 <@gmaxwell> HM: sure it is. It is always successful. And if it fails you reboot. :P Have you not done embedded system design?
17:37 < HM> oh right, that's how it's done
17:39 < HM> this is boned
17:39 < HM> i'm running 50 copies of a client binary to test a servers fairness
17:39 <@sipa> hmm, how hard would it be to make bitcoin depend on GMP?
17:39 < HM> the clients are quitting after 1 minute
17:39 <@sipa> it's LGPL
17:41 < HM> LGPL is fine?
17:41 <@sipa> first check why they get such good performance, maybe a similar algorithm can be implemented directly
17:41 < HM> one instance takes 7 seconds, 100,000 iterations
17:41 <@sipa> but 160us -> 130us is pretty significant...
17:41 < HM> 50 instances seem to finish in 1 minute...
17:42 < nanotube> <gmaxwell> The old and now increasingly depricated internet "be forgiving in what you accept" <- yea, that always struck me as introducing some perverse incentives. :)
18:05 <@gmaxwell> nanotube: it's widely considered to be a bad idea now in many circles, esp anywhere in remote proximity to HTML.
18:06 <@gmaxwell> in IETF meetings people will say something like that and then get called out "no, we used to think that. And now we know were were stupid."
18:06 <@gmaxwell> inexactness means you need a faithful emulation of every set of possible bug permutations, rather than just exact emulation of the bugs in the standard. :P
18:09 <@gmaxwell> 14:32 < HM> the STL containers let you use custom allocators
18:10 <@gmaxwell> Because they have exposed non-normative (implementation defined) behavior.
18:11 <@gmaxwell> conformant software could be written which can detect which STL implementation it uses. Which means if they are used care must be taken to make sure none of that behavior leaks into the externally visible behavior of the system.
18:21 < HM> why is this a problem for a blockchain server
18:21 < HM> i'd rather have a system faulty and fault tolerant than something coded for the space shuttle but written like it's the 70s
18:26 < HM> i agree generally on external libraries though
18:33 < midnightmagic> be fogiving in what you accept implies that imperfectly-specified standards (even SUSv3 has endless argument around it requiring clarification notes from Austin group) don't force everyone else to conform to your interpretations.
18:34 < midnightmagic> it's not particularly evil to allow something outside your state machine to come in, and discard it, it promotes interoperability.
18:34 < midnightmagic> HTML is something else.
18:35 < nanotube> <b>what you <i>say</b> about html?</i> :)
18:41  * nanotube suspects that the badly formed html just killed everybody's clients. or brains. >_>
18:44  * sipa reboots
18:45 < HM> be forgiving in what you accept
18:46 < HM> or whatever the correct quote is, merely means accepting the reality of imperfect implementations
18:47 < HM> imagine if a bitcoin implementation had a bug in it that was subtle and hard to discover
18:47 < HM> and 50% of the network began using that implementation
18:47 < HM> if you're overly strict and just exit when that bug is detected half your network vanishes
18:47 < HM> sometimes limping on, when it doesn't damage integrity, is just better
18:49 < nanotube> HM: missing a step there. before it gets to 50%, the first guy who uses it and realizes nobody is seeing his transactions, will report the bug if everyone is strict.
18:49 < nanotube> it'll only get to 50% if everyone is not strict
18:50 < nanotube> but i guess if bug only happens very rarely... it's possible.
18:51 < HM> *exit or disconnect
18:51 < nanotube> but then i don't know if it's actually better to accept some invalid transactions just because 50% of the network is using a buggy implementation that thinks it's valid.
18:53 < nanotube> probably best to respond with some error msg, rather than quietly disconnecting
18:55 < HM> it depends on the bug
18:55 < HM> i mean with bitcoin you could be talking about crippling and economy
18:55 < HM> bad software gets widely used, this is an unavoidable fact
18:56 < HM> users are slow to patch and upgrade
18:56 < HM> being liberal in what you accept just makes life easier
18:57 < HM> i don't know who came up with the original phrase, or what they were referring to, but i always take it to mean tests should focus on output as well as input
18:57 <@sipa> HM: that problem is one we'd have today if one implementation uses openssl and another uses something elae
18:57 <@sipa> and they are compatible for every use that exista in the chain
18:57 <@sipa> but there is one weird corner case, that nobody knows aboit, which openssl accepts and another implememtation doesn't
18:59 < HM> what is that?
21:11  * sipa just corrected a bug in an algorithm on wikipedia!
21:22 < HM> lol which one?
21:22 < HM> the sad thing is i probably learned it from it
21:23 <@sipa> http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#wNAF_method
21:30 < HM> no Monty Ladder?
21:32 <@sipa> no need for a constant-time algorithm when verifying
21:33 < HM> true
22:10 <@sipa> 126us \o/
--- Log closed Mon Mar 11 00:00:49 2013