--- Log opened Thu Jan 09 00:00:17 2014
01:17 < justanotheruser> Has anyone made any proposals for anonymity networks upon which things like coinjoins and coinswaps could take place?
01:22 < michagogo|cloud> I left the Jesuscoin-killing script (replaying the Bitcoin blockchain) running overnight
01:23 < michagogo|cloud> Only gotten as far as block 234853
01:25 < justanotheruser> michagogo|cloud: nice, you actually made the magic changing thing
01:26 < michagogo|cloud> justanotheruser: I actually tweaked linearize.py to do that
01:26 < justanotheruser> michagogo|cloud: does jesuscoin have a community at all?
01:26 < michagogo|cloud> But before I actually ran it, I realized that I didn't need to
01:26 < michagogo|cloud> This script also works: http://0bin.net/paste/OFWqJ7Lj0k0GO0o4#Rd6uP8VFxwv3SEO4HQAwtF+Vy5M3ZtaUrrKC9m3qI+w=
01:26 < michagogo|cloud> justanotheruser: Not really, afaik
01:27 < justanotheruser> michagogo|cloud: Is this only possible because jesuscoin has all bitcoins defaults?
01:27 < michagogo|cloud> justanotheruser: Yes
01:27 < michagogo|cloud> It's a 100% clone of Bitcoin
01:27 < michagogo|cloud> Specifically the genesis block and parameters
01:29 < wyager> Oh my god
01:29 < wyager> that is so stupid
01:29 < wyager> And hilarious
01:31 < justanotheruser> heh
01:31 < justanotheruser> I wonder why no one did this for ixcoin or i0coin
01:31 < justanotheruser> well I guess ixcoin had a premine, but i0coin it might be possible
01:58 < justanotheruser> Bitcoin currently only allows turing incomplete scripts. Please tell me why an altcoin that has a limit on both block size and cycles executed to verify a blocks transaction (allowing turing complete scripts) is a bad idea.
03:35 < nsh> justanotheruser, it's not a bad idea, experimentally. it might be a foolhardy store of value
03:36 < justanotheruser> nsh: why?
03:37 < nsh> because there's no explicit incentive analysis that guarantees behaviour converges towards the subset of actions that preserve integrity
03:38 < nsh> there could be weird effects that stop people self-interestedly cooperating to keep value stable
03:38 < nsh> (there could also not)
03:38 < Taek42> technically, if you limit the number of cycles then it's not turing complete
03:41 < justanotheruser> Taek42: the scripts were never turing complete
03:42 < justanotheruser> and there can only be a limited number of scripts per block, therefore the blocks were never turing complete
03:42 < Taek42> I know that, was just knit-picking
03:43 < justanotheruser> Taek42: oh, I misunderstood. You were referring to my original statement where I said this could be turing complete.
03:43 < Taek42> I was wondering if it would be possible to build a higher-level lanugage on bitcoin script
03:43 < Taek42> right
03:43 < Taek42> Image a C-like that output bitcoin-script instead of assembly
03:43 < stonecoldpat> michagogo|cloud: jesuscoin i love it
03:43 < justanotheruser> Yes, it wouldn't be turing complete, but it would allow for turing complete scripts that get cut off if they run too long (so pseudo-turing-complete)
03:44 < justanotheruser> well not cut off, but only be accepted if they have a limited run time
03:44 < Taek42> As long as you have a reliable way of measuring where the scripts get cut off
03:44 < Taek42> because all hosts would need to agree if a script took too long to terminate
03:44 < justanotheruser> Taek42: it would be like measuring where transactions get cut off. The miners determined it
03:44 < justanotheruser> (in terms of size)
03:45 < Taek42> hmmm
03:47 < justanotheruser> The transactor could say how many cycles the script should take in the header. If it takes more than that, then the miner can spend the transaction themselves maybe? (This is the best way I can think of preventing DoSing miners with large scripts
03:47 < justanotheruser> I suppose that would limit the ability to give people scripts that they can spend later though
03:48 < justanotheruser> well actually nvm the statement directly above this
03:48 < justanotheruser> you should build these scripts so they can't run arbitrarily longly, otherwise someone will donate the tx to miners
03:49 < justanotheruser> nsh: Are you saying this system would hurt stability of the price?
03:50 < nsh> not necessarily, just that things tend toward instability as the degrees of freedom increase
03:51 < justanotheruser> nsh: when you say degrees of freedom do you mean it in the mathematical sense, or could I substitute degrees with amount?
03:51 < Taek42> nsh I'm not sure I agree with that
03:52 < nsh> mathematical, but perhaps i'm wrong
03:52 < nsh> certainly in mechanical dynamic systems you are more likely to exhibit chaotic behaviour when you have more (dynamically coupled) degrees of freedom
03:52 < justanotheruser> nsh: could you explain what a degree of freedom is in these terms then?
03:53 < nsh> "In mechanics, the degree of freedom (DOF) of a mechanical system is the number of independent parameters that define its configuration. It is the number of parameters that determine the state of a physical system"
03:53 < justanotheruser> nsh: Are you saying bitcoin price would be more stable if it didn't have p2sh?
03:53 < nsh> no
03:54 < justanotheruser> doesn't p2sh add a DOF?
03:54 < nsh> the price stability derives from the network stability, which derives from everyone's behaviours being constrained (by "enlightened self-interest") to keep things working in some defined manner
03:55 < nsh> yes, but you're making stronger assertions :)
03:55 < Taek42> depends on what you mean by network
03:56 < justanotheruser> nsh: Does another DOF hurt network stability?
03:56 < Taek42> bitcoins price instability derives from the fact that the volume in circulation can't adjust to the demand
03:56 < Taek42> and the demand has been all over the map
03:56 < nsh> justanotheruser, depends
03:56 < nsh> what i proposed was that as the number of DoFs increases then the entire system _tends_ towards more unstable behaviour
03:57 < justanotheruser> hm
03:57 < nsh> to go from that to saying adding one DoF neccessarily increase instability requires some additional evidence
03:57 < justanotheruser> I'm not sure if I agree with you. I don't think it makes in less stable unless it makes it less secure
03:57 < nsh> and anyway, i'm probably just smoking crack
04:00 < justanotheruser> Another advantage I see in this is a limit on CPU intensive scripts. No longer will we have to worry about transactions that take a long time to validate but are inexpensive because they take up little physical space
04:19 < sipa> the reason why turing complete scripts are a bad idea is because you cannot determine the cost of running without running
04:19 < sipa> even if it's not actually turing complete and limited to some high amount of cycles
04:21 < nsh> which means easy DoS attacks?
04:22 < Taek42> If you had it in a sterile environment (no malware issues), I would think that the only problem would be large scripts (too much data) or long scripts (too much runtime)
04:23 < Taek42> wouldn't limiting the cycles prevent that?
04:27 < sipa> if one transaction costs 1000 times more to validate than another, you need pretty good policying to make sure it is deincentivized
04:31 < Taek42> or you could charge each transaction equal to the theoretical limit on how expensive it is
04:31 < Taek42> then the miners will be happy
04:31 < Taek42> or you could wait to charge until you know how many clock cycles were spent validating it
04:35 < sipa> the problem is that mining is constrained by size, so will end up picking transactions with sufficient fee per byte
04:35 < sipa> if you want the same incentive for execution, you need a hard limit per block on validation cost
04:35 < sipa> which complicates optimal transaction selectiom
09:40 < petertodd> sipa: I really don't see what the big deal is; you have to execute the script anyway yourself to validate that the transaction is valid. Adding opcode counters to Eval() isn't a big deal.
09:40 < petertodd> sipa: sure there's some theoretical static analysis stuff you could do, but it's consensus critical - keep it simple and stupid
09:53 < andytoshi> petertodd: suppose i make a script which has fee for 100000 iterations, but runs for 100001, so it can't validate
09:53 < andytoshi> is there a nice way to prevent a DoS along those lines?
09:54 < petertodd> andytoshi: probably not, but at least that's a local DoS attack - lots of those
09:55 < petertodd> andytoshi: anyway, a csript can't exceed the limit for a whole block by definition, and block propagation has to be fast, thus it can't be that much of an issue
09:55 < andytoshi> yeah, fair enough, i guess people are free to make IsStandard reject anything that might take too long for their system
09:55 < andytoshi> also a good point
09:55 < petertodd> andytoshi: yup
09:56 < petertodd> andytoshi: and static analysis is all well and good, but like I say, it'd be in consensus critical codepaths...
09:57 < andytoshi> yeah, perhaps it's a meta-problem that people will try to do it if they see a benefit
09:57 < petertodd> lol!
09:58 < andytoshi> the real problem i see with turing-completeness is that the block limits you'd have to put on it are too stringent for anything cool to be done
09:58 < andytoshi> OTOH if we could do snark-validation so only one person (potentially the transactors themselves) ever have to compute it, i'd be happy with it
09:58 < petertodd> yeah, but like I say, until we get SCIP you have to have limits because you have to actually run the code to validate! turing completeness has nothing to do with that
10:22 < gmaxwell> andytoshi: certantly the block limits you'd have to have would be too stringent to do anything interesting if the instruction set weren't very high level, and if we had to assume execution via a very dumb interperter.
10:22 < gmaxwell> the latter is probably true, the former not so much.
10:23 < gmaxwell> This isn't to say I'm necessarily a fan of turing complete script. I do think getting an execution counter right is hard.
10:23 < petertodd> gmaxwell: just do a MAST design and make sure your MAST hash function is more costly than anything else...
10:24 < adam3us> btw about pegged side-chain, i think the actual spv proven side->main protocol would not need to be run.  its just a threat that it could be run.  cross chain-atomic swaps can do the actual swap.  and market makers can do it.  if volume dries up or mkt maker low on funds he can clear via side->main spv proof.
10:24 < nsh> petertodd, what's MAST?
10:24 < gmaxwell> adam3us: it needs to be run some, but perhaps not much.
10:24 < petertodd> nsh: merkleized abstract syntax tree
10:25 < nsh> ah, ty
10:25 < gmaxwell> petertodd: I don't think it would be efficient to force every branch to be mast, besides loops with unknown depth can't be seperately mast-ed.
10:25 < adam3us> gmaxwell: yes.  it depends on the willingness of mkt maker to hold btc funds  someone with big long term btc holdings anyway would be willing to mkt make all-day-long for 0.1% or whatever, its near free risk free money for executing a script.  its a form of interest for btc holdins
10:26 < petertodd> gmaxwell: which is my serious point: turing completeness often gives you more efficient code in cpu and code size
10:26 < gmaxwell> adam3us: I mean, you'd need to have at least one execution to get funds there in the first place.
10:27 < gmaxwell> petertodd: certantly low level opcodes do not.
10:27 < gmaxwell> adam3us: but yea, that was part of my point when we previously discussed. It can be expensive because it's not a primary daily mechenism.
10:27 < adam3us> gmaxwell: agreed.  mkt makers might need to do rare large tx in which ever direction is leading to a liquidity exhausting direction.  but the mkt maker spread should be tiny as anyone holding btc can do it, and they can do it with airgap security if they want trezor/armory so there should be lots of security
10:28 < adam3us> gmaxwell: agreed.  i think everything i just said was in the original thread.  just emphasizing how cool that is :)
10:29 < gmaxwell> sipa: I think you could perhaps resolve the selection complication by just counting each byte as one instruction too, and have only an instruction limit. Then at least the optimization can remain in one dimension.
10:29 < gmaxwell> I still think implementors will totally screw up their instruction counting, esp when slower scripts start driving them ot JIT.
10:30 < gmaxwell> it might help if every signature needed to have its final instruction count with it, and they're forced to match exactly.
10:30 < adam3us> gmaxwell: its the missing part of my hypothesis that a 1-way peg is already close to plausible for mkt maker to fill the gap, if there is eg some long term chain migration plan.  in this way no migration is necessary.
10:32 < adam3us> gmaxwell: pay per cycle.  yes seems plausible, but may create lumpy work load for nodes.  maybe processing with in a given time-frame becomes critical to the semantics of the tx even.  the point of TC would be to use it as a meta-programming language to define new coins and rules.  eg in this kind of system something like p2sh change is just a script with no system code changes.  a script can define a new concept
10:33 < gmaxwell> yea, I'm still not arguing letting validation become expensive is a good idea. :P  Just filling out the idea.
10:34 < adam3us> gmaxwell: but u have to wonder about the safety of that.  btc script is intentionally constrained and even then people were value scared enuf to disable most of it.  general script are even disabled right (only certain pre-cooked ones allowed)?  this on the other hand may allow a clever set of scripts to attack each other, and
10:35 < gmaxwell> Implementers currently get script execution all wrong and it's already quite simple.
10:35 < adam3us> gmaxwell: so somone creates a btc/usd call option, and someone else creates another script to do something else or a competing call option and it steals all the money from the other call options.  its like redcode
10:36 < petertodd> adam3us: I don't think we're ready to have scripts run on thier own - creates consensus issues about when a script is supposed to run!
10:38 < adam3us> gmaxwell: even if the interpreter is correct (single implementation = spec satoshi style) i am not sure about the redcode game issue
10:38 < petertodd> redcode game?
10:39 < adam3us> petertodd: never played it but http://en.wikipedia.org/wiki/Core_War
10:39 < petertodd> adam3us: ah! yeah that's a classic
10:39 < adam3us> petertodd: users battle for control of the cpu with hostile code
10:40 < petertodd> Interesting thought: transactions and the blockchain are a way of stringing multiple bits of code together in a DAG.
10:41 < gmaxwell> adam3us: certantly that kind of ecosystem would create greater incentives for reorgs.
10:42 < andytoshi> petertodd: i have thought about making a blockchain-based haskell-like language
10:42 < andytoshi> sadly, i could see no point to it
10:43 < petertodd> andytoshi: I had the similar idea of doing a HSM with merklized forth actually - pretty much the exact opposite direction in terms of implementation complexity
10:45 < andytoshi> hsm == Hierarchical storage management ?
10:45 < gmaxwell> hardware security module
10:46 < andytoshi> gmaxwell: ah, that's what i thought, but i didn't see the connection to merklized forth
10:46 < adam3us1> gmaxwell: but even if (hypothetically) the incentives worked, and the interpreter escape issue was magically solved, and program counter issues avoided... i am still wondering if its fundmentally unprovably dangerous
10:46 < petertodd> andytoshi: it's more because forth is incredibly simple, so it's more likely you'd actually get the implementation right
10:47 < adam3us1> gmaxwell: see i mean it defines a language for writing bitcoin functions, new script functions, new semantics for value transfer or whatever, its fully general; but in such an environment would u not be in a core-war / redcode scenario is my point
10:47 < petertodd> andytoshi: yet forth still can do lisp-like tricks by doing data as code
10:48 < andytoshi> petertodd: oh, i see
10:48 < andytoshi> i should've looked up forth instead of hsm :P all i know is 'stack-based language'
10:48 < gmaxwell> adam3us1: I'm not sure if it would be core-war or not. If resource constraints work they'd be fighting the resource constraints not each other. Certantly lots of people would lose money by writing dumb code that can be tricked. "LOL I integer overflowed your transaction and took all your monies!"
10:49 < adam3us1> gmaxwell: its almost but not quite, like you linked a remote execution of java byte code for fees and feature extension ito the bitcoinj - in theory flexible - in practice dangerously generic
10:49 < gmaxwell> and yes, I think it would be very very hard to make safe in a single implementation, and exceptionally hard to safely reimplement.
10:50 < adam3us1> gmaxwell: i mean that one could just take your private key and be done.  but yes exactly, the question is beyond that even competently written script extensions written in a generic jvm bytecode kind of level be systematically safe from any other byte code string that could be later run in the competing ecosystem
10:50 < gmaxwell> This is why I prefer the path of using SNARKs of some kind for more complex scripts.
10:50 < andytoshi> it seems that any instance of 'breaking out of the sandbox' would be a forking scenario, since it'd probably depend on the memory layout of the targets
10:51 < gmaxwell> adam3us1: I mean, right now eligius isn't using a multisignature address for the emergency pool address because they don't know how to go forward on making sure their prefered script formulation is safe.
10:51 < adam3us1> gmaxwell: well snarks just mean that u dont run the code, you run the verifier on the proof the code was run; it still vulnerable if it is as self-extensible as TC arbitrary vm bytecode level code
10:52 < petertodd> gmaxwell: you mean they don't have the tools to just go make a scriptSig to try spending it?
10:52 < gmaxwell> andytoshi: maybe, overwriting the behavior of one other opcode might be possible just with a constant offset.
10:53 < gmaxwell> petertodd: they want to have a    {a and b} or {{a or b} and 2 of 3{c,d,e}}   sort of script. They came up with one, but were not completely confident that their coding was flawless (or if unexpected behavior in op_if would let funds get stolen)
10:54 < gmaxwell> adam3us1: at least there is no "code escape" bug in the snark case. Or consensus-criticial-implementation-consistency bugs.
10:54 < andytoshi> adam3us1: are you talking about finding bugs in the snark circuit (which is commited to in the preprocessing stage) itself?
10:54 < petertodd> gmaxwell: ah, did they do the "op_if" as "select block of code" style?
10:54 < gmaxwell> only the risk that you write a bad script.
10:54 < adam3us1> gmaxwell: i am thinking it may have even some mathematical provability limits.  if u consider the near infinite (finite because of program counter limit per time-slice)  set of computable functions how can you generically prove that there exists no other function that can damage teh intended properties of the former extension function when used by anyone.
10:55 < adam3us1> gmaxwell: correct on the code ecsape and interpretation fork
10:55 < gmaxwell> petertodd: they did two checksigs and accumulator to count how many worked, and if its not two, they drop into an op_if block that checks the accumulator for one, and runs a check multisig.
10:55 < adam3us1> andytoshi: no i am just saying if each and every user can go wild and create bitcoin script language extensions dynamically how do u know the resulting ecosystem will be safe after each dynamic new feature is added.  it is maybe mathematically undecidable
10:56 < gmaxwell> adam3us1: sure, or—  "You can steal my coins if you can find the discrete log of 0xdeadbeef"
10:56 < andytoshi> adam3us1: oh, gotcha, still on the redcode scenario
10:57 < petertodd> gmaxwell: right, see I would do that as op_if 2 a b checkmultisig else if a checksigverify else b checksigverify endif 2 c d e 3 checkmultisig endif
10:57 < adam3us1> gmaxwell: but these TC extensions are stateful.  so if there is any rational logic to disabling simple things like XOR script, this is like letting anyone define new opcodes and higher level functions running arbitrary byte code.  how is that safe in comparison
10:58 < petertodd> gmaxwell: spend with sig_a sig_b 1, or with: sig_c sig_d (sig_a or sig_b) 1/0 0
10:58 < petertodd> gmaxwell: no accumulator needed
10:58 < gmaxwell> petertodd: well that form repeats the pubkeys a fair bit.
10:59 < petertodd> gmaxwell: yes, but it's very simple to understand
10:59 < gmaxwell> adam3us1: yea, I can't justify stateful things.
10:59 < gmaxwell> petertodd: but ... we want to both have and eat the cake.
11:00 < petertodd> gmaxwell: lets see if we can succesfully eat a muffin without losing tens of thousands of dollars
11:00 < gmaxwell> petertodd: in any case, it's an issue that the ability to safely use fancier scripts is that they're moderately risky.
11:01 < gmaxwell> but (1) my comment was also an existance proof that people are actually smart enough to realize this (2) it's sort of their own problem if they don't.
11:01 < petertodd> gmaxwell: well that's just inherent to doing complex things
11:01 < andytoshi> i thought the rationale for having disabled opcodes is that they could screw with the people running the code (i.e. everyone) to cause either DoS attacks of some form, or worse, forks
11:01 < gmaxwell> (It wasn't me who pointed out that script was risky either, I think)
11:01 < andytoshi> but in case of snarks, everybody is just verifying that a specific (TC-complete) circuit was run
11:02 < gmaxwell> andytoshi: we disabled the op_codes because lshift was exploitable to crash nodes.
11:02 < petertodd> andytoshi: the rational was "oh shit! lets be super cautious now"
11:02 < gmaxwell> It turns out that some of the other disabled ones had other bugs too.
11:02 < petertodd> andytoshi: lshift could have been fixed, but just disabling was easy
11:02 < petertodd> andytoshi: back then I don't think people fully understood how hard re-enablingthem would be
11:03 < adam3us1> gmaxwell: what next.  google nacl (sandbox execution of x86 binaries).  activex for bitcoin :)
11:03 < andytoshi> well, i'd hope that we donet have OP_OPENNETWORKPORT ;)
11:03 < gmaxwell> adam3us1: the pressure to implement fast JITs for this stuff is part of the reason I'm skeptical about people getting the cycle counters right.
11:04 < adam3us1> andytoshi: this is more like OP_FORMATDISK, OP_SENDPRIVATEKEYS
11:06 < adam3us1> gmaxwell: the nice thing about cross chain atomic swap as the main mechanism is its full-node secure (not just spv) and its the market makers who are taking the SPV risk
11:06 < adam3us1> (back on the pegged side-chain again)
11:06 < gmaxwell> in any case, with snarks I think you're just left with people may right scripts which are unsafe in a mean and nasty world, and I'm okay with that. I don't think we can do better without removing all flexibility. Hell, even DSA is not really safe in a mean and nasty world. :)
11:07 < gmaxwell> adam3us1: hm. well atomic chain swaps are not secure against sufficently reorgs with double spends... but they are a 1:1 risk, only the person swapping with you can rip you off.
11:07 < gmaxwell> er sufficiently deep reorgs.
11:08 < gmaxwell> Right the first step of an atomic swap is to multisig escrow coins.  If you suffer a reorg deep enough that the escrowing can be killed on one chain, after the transaction is done on the other, the coins can be clawed back.
11:08 < gmaxwell> it's just not a doomsday risk
11:09 < nsh> so.. i guess OP_DOOMSDAY is completely out the window?
11:09 < adam3us1> gmaxwell: i am not 100% sure, though there is some plausibility, that you can expect to extract secure finance in a distributed version of core wars/redcode, even with user action on input for private keys, private key crypto ops outside of the sandbox, sandboxes for execution.  non-functional statefuul code in a hostile distributed execution environment plus a bit of crypto
11:10 < petertodd> adam3us1: my first question: what is all this going to actually be used for?
11:27 < justanotheruser> hello
11:35 < adam3us1> petertodd: its going to be used say to encourage an explosion of innovation, by making TC code maximally self-extensible.
11:39 < adam3us> petertodd: alternatively a fun experiment in core-wars/redode with $Bns at stake, or exploring the boundaries of human ability to write secure code in a hostile environment & formal provability of security properties of code
11:39 < petertodd> true!
11:39 < petertodd> corewars where you atually lose money if you lose
11:48 < jtimon> very interesting, I hadn't thought about the scripts as a source of consensus-criticial-implementation-consistency bugs
11:48 < jtimon> I'm not sure I understand the corewars attacks though
11:49 < jtimon> say I pay to a p2sh and the script is TC
11:50 < jtimon> the attacker still has to find a script with the same hash, no?
11:50 < jtimon> what am I missing adam3us1 ?
12:21 < jtimon> I guess I don't understand the corewars game itself
12:23 < adam3us> jtimon: corewars i never played either but the idea is to seize control of the cpu or the other guys program.  a game of hostile code vs hostile code
12:24 < jtimon> yeah I understand the general idea, I'm not sure I udnerstand the strategies though
12:26 < jtimon> anyway, apart from gmaxwell's concerns (code scape and script-consensus), what are the potential problems with a TC p2sh ?
12:26 < gmaxwell> I have actually played corewars.
12:27 < gmaxwell> (on an atari ST, I believe)
12:27 < jtimon> the game looks very interesting
12:27 < adam3us> adam3us: if TC extensions can be written by anyone dynamically at any time to the opcode, script lang etc and the TC is persistently statefull i was wondering if an existing op code or smart-contract can convince its author that it cant be later fooled by someone elses state changes, extensions etc.  TC is a lot of complexity.
12:30 < adam3us> jtimon: wait quark has its own PoW?
12:31 < jtimon> TC is all the complexity :) I'm still not sure I understand what you mean though :(
12:31 < jtimon> yes, I think so
12:31 < jtimon> a "basket algorithm"
12:31 < jtimon> some freicoiners pushed for something similar for a while
12:33 < jtimon>  instead of using just one hash function as Bitcoin does, Quark uses six: BLAKE, Blue Midnight Wish, Groestl, JH, Skein and Keccak.
12:33 < adam3us> jtimon: oh maybe i heard of that some mix, yes
12:33 < jtimon> http://bitcoinmagazine.com/8972/quarkcoin-noble-intentions-wrong-approach/
12:37 < jtimon> I don't know adam3us, if you're hashing your own TC script, why would you fool yourself?
12:37 < brisque> https://ghash.io/ghashio_press_release.pdf
12:39 < brisque> 45% private hardware is interesting though, gmaxwell wasn't wrong about the amount of funding selling hardware gave them
12:39 < gmaxwell> "Jeffery Smith"
12:39 < pigeons> Tom Williams
12:40 < jtimon> can't they just p2pool? is 55% p2pool risky?
12:40 < brisque> no.
12:40 < brisque> if ghash.io dumped their load on p2pool they would rocket the share difficulty though.
12:41 < jtimon> I see, it's a question of efficiency
12:41 < brisque> gmaxwell: different name than on their domain at least.
12:41 < gmaxwell> brisque: well it's not that bad because p2pool adapts share difficulty per miner somewhat.
12:42 < brisque> good point.
12:43 < jtimon> Interesting: "Non-standard transactions, such as mentioned above, can not be relayed to
12:43 < jtimon> the blockchain network, however they are still valid, and can be mined
12:43 < jtimon> using the hashing power accumulated on GHash.IO. "
12:44 < adam3us> jtimon: point is if everyone can extend the script language at any time, and write to global, persistent state (presumably with some authorization) are we still as confident that a smart-contract cant be tricked by another persons script or state chagnes.  probably not as sure.  maybe not very sure at all.
12:44 < brisque> jtimon: not much help if there's no publicly known nodes to push to though. eligius has an interface for it.
12:46 < jtimon> adam3us what you mean a persistent state? apart from the utxo itself? Like a global "general purpose in-chain memory" or something?
12:46 < adam3us> jtimon: yes.
12:47 < jtimon> and why is that persistent state needed for?
12:47 < jtimon> I thought we were only assuming TC scripting
13:52 < maaku_> gmaxwell: "p2pool adapts share difficulty per miner" is that true? i thought the current share level was part of p2pool's consensus.
13:52 < gmaxwell> maaku_: there is a minimum share difficulty and a maximum share difficulty (just a multiple of the minimum) which is part of the consensus.
13:53 < gmaxwell> maaku_: but indivigual miners can choose any difficulty in between the two, and the stock software targets getting a certian number (1000? I forget) of shares in the window.
13:54 < maaku_> ah
13:55 < maaku_> re TC complete scripts, is there any known application of this stuff?
13:55 < gmaxwell> The end result is just that the minimum is lower than it would be if everyone used the minimum... and large miners give up a small amount of share variance by default, but it makes the variance much lower for small miners.
13:56 < gmaxwell> maaku_: not really. I mean, if bounds are high enough it expands the space of non-private non-interactive bounty transactions. e.g. "100 BTC to someone who provides the root key to AACS"
14:00 < maaku_> gmaxwell: short of that stuff, which is probably best done with a SNARK verification opcode, it seems like most of the benefits could be had via MAST & loop unrolling
14:01 < gmaxwell> maaku_: yea, personally I don't see a lot of point to turing complete. The lack of privacy really closes a lot of options that would otherwise be interesting.
14:01 < gmaxwell> And a lot of stuff can just be done with simple finite state which could be represented in a fixed script (and, indeed, MAST compressed)
14:03 < gmaxwell> I'm more interested in questions like "How can you encode a boolean satisfaction rule like (x and y) or ((x or y) and 2 of 3 (a,b,c))  most compactly.
14:05 < maaku_> that would be directly useful
14:08 < gmaxwell> Coding those kinds of rules via procedural branching is not terribly compact.
14:08 < midnightmagic> truth-table optimization and karnaugh maps?
14:11 < gmaxwell> The naive way is to encode a truth table, but its exponential in the number of variables.
14:12 < gmaxwell> I suppose that a 32 bit truth table for 5 inputs would still be smaller than any way that script can express the above rule.
14:18 < midnightmagic> oh right.. "like".
14:18 < gmaxwell> hm. perhaps efficient encoding of the satisfaction rules is less interesting than I was thinking. The reason is that when the rules can be reorded so that you can avoid disclosing >1 public key, then you're better off MAST compressing that part of the rule.
14:20 < gmaxwell> e.g. you could have a OP_TABLE that took in 5 bits encoding x,y,a,b,c signatures passing and a 32 bit table value, ... but it would result in a larger script than a procedural one that only disclosed the a,b,c pubkeys if !(x&&y).
14:21 < midnightmagic> truth table optimization and piles of interesting technique for it are covered in digital logic design texts such as .. hrm. I can't find it anymore. Well, mine has this guy with a hat, and in the other side, the picture is inverted and the guy is gone and there's blue sky revealed behind the cutout.
14:23 < nsh> i don't think i've ever remembered a book cover in such detail...
14:23 < gmaxwell> I wonder if there is a efficient way to represent truth tables that are never 'too indifferent'... e.g. wouldn't be better represented by a MAST. My head hurts.
14:23 < nsh> hmm
14:24 < nsh> what's indifference in this context, gmaxwell?
14:25 < gmaxwell> nsh: e.g. in the truth table for (x and y) or ((x or y) and 2 of 3 (a,b,c))    if x&&y or !x && !y  then it doesn't matter if a,b,c are true.
14:25 < nsh> ah, right
14:26 < gmaxwell> so if you were to make a script that encoded (x and y) or ((x or y) and 2 of 3 (a,b,c)) you would probably want to use a branching script that revealed a,b,c pubkeys if and only if x^y
14:27 < nsh> hmm
14:28 < gmaxwell> e.g. coding 5 checksigs and then a truth table over them would likely not be the best way to represent that multisig.  The truth table is smaller than the branching stuff, but if we had hash compression of untaken branches the branching stuff would be smaller.
14:29 < gmaxwell> So I was wondering if there might be an efficient representation for truth tables where that _wouldn't_ be the case, e.g. where no 1 bit prefix can factor out at least two of the interior tests.
14:30 < gmaxwell> e.g. there is no such x input wire that makes the table insensitive to more than two or more other wires.
14:31 < nsh> beats me
14:34 < Taek42> Would Pierce's logic help any?
14:45 < amiller> i'm interested if anyone here has looked at ethereum http://ethereum.org/ethereum.html
14:45 < amiller> vitalik's attempt at making a broader script language for contracts
14:46 < amiller> the main interesting thing is you can have a "contract", which is like a persistent utxo, it receives data inputs from transactions, it has a special register-like thing representing a "balance" of conserved currency, and it can contains instructions that "send" from that balance to some other contract
14:49 < pigeons> i dont know what can be done about it, and obviously its not a technical issue, but when i look at different smart contract proposals, not usually directly bitcoin related, i wonder about how sometimes a party to the contract would need to be an expert in the execution platform and the language to be sure the contract he is agreeing to, maybe written by the other party will do what he expects. i guess that's no different than "real world" "du
14:49 < gmaxwell> pigeons: you got cutoff at than "real world" "du
14:49 < pigeons> real world "dumb" contracts
14:50 < pigeons> not that anyone can protect everyone from potential ripoffs all the time, but some people would try to fool people. contract does X, but it does not
14:50 < gmaxwell> pigeons: but sure, part of the point is that "standard" contracts can be formed which get reviewed by experts. But its absolutely an issue, and its part of the reason that the simple forth-like encoding in bitcoin is pretty good— simply becasuse it actually isn't TOO terrible for the right kind of expert to evaluate them.  Likewise, their non-turing completeness makes it possible to make tools that analize them and present to you ...
14:51 < gmaxwell> ... all the ways of satisifying them.
14:51 < pigeons> right
14:59 < maaku_> gmaxwell: if you allow non-valid pubkeys and sigs for the ones which are not required, isn't that enough?
14:59 < maaku_> e.g. the pubkey script is OP_TABLE for x,y,a,b,c
15:00 < maaku_> the scriptSig is x-pubkey x-sig y-pubkey y-sig OP_0 OP_0 OP_0 OP_0 OP_0 OP_0
15:00 < maaku_> er-no, you need to check that the pubkeyhashes match, nevermind
15:01 < andytoshi> amiller: i've seen it mentioned a few times here, so i think somebody (not me) has looked into it
15:02 < amiller> ok. it's possible i've pasted it here before too.
15:02 < amiller> having a) contracts that persist through multiple transactions and b) a way of sending value from one to another are both new
15:02 < amiller> and far more relevant to discuss imo than the red herring of turing completness
15:03 < maaku_> well, open-txns does that
15:03 < maaku_> but new as a bitcoin proposal i suppose
15:03 < maaku_> it fails spectacularly at managing DoS potential with its TC scripts
15:03 < gmaxwell> amiller: well I think the covenants post I made shows the kind of farscial mess you can make with that stuff.
15:04 < gmaxwell> I'd be more interesting in someone giving a clear example which can't just be replaced with an interactive protocol.
15:04 < amiller> chess game
15:04 < gmaxwell> I'm sure ones exist, but I mostly drew a blank.
15:05 < amiller> the reason you can't do multiple round protocols with bitcoin including covenant script is that you can't condition future txouts on the current txout
15:05 < gmaxwell> amiller: what, you have the program verify your chess witness?  One of the players will just stop moving once he sees that he'll lose but before the transcript is finished, — exponential advantage for cheating.
15:06 < amiller> ok so you do the standard trick for adding fairness by having a move timer
15:06 < amiller> if you fail to publish a valid move within k blocks you forfeit
15:08 < gmaxwell> amiller: okay, fair enough.
15:08 < amiller> so. maybe it's still possible to do this with covenant
15:08 < amiller> because you can make the input claimable with evidence that there is a blockchain with sufficient length that includes corresponding transactions etc. whatever
15:09 < amiller> maybe you can always transform any other smart-contract system into one with the current semantics and using chain proofs like that.
15:09 < gmaxwell> amiller: in any case, its _always_ possible without making the network evaluate turing complete code, because you can just outsource script processing via a snark.
15:10 < amiller> yes turing complete is completely irrelevant here
15:11 < amiller> i think the semantics of the chess game example are pretty clear and that makes it a good example, it's just not an obvious business case financial impact kind of thing, that's the only problem with it
15:11 < gmaxwell> Then what is? you can allow arbritary data from the chain just by extracting it and presenting it to the program.
15:11 < amiller> including a proof that a suitable transaction doesn't exist?
15:12 < amiller> like if i wanted to time out the player who fails to publish a chess move, i would want to show that the current chain has k blocks and does not contain a valid move
15:12 < gmaxwell> why would you even publish the moves? you'd use a dominating spend like I proposed for anti-cheat in the coinwitness thread.
15:13 < gmaxwell> Basically if someone tries to time out redeem the game, the output is covenant locked so that it can be spent by either a longer witness or after a final timeout.
15:14 < gmaxwell> Was I clear enough there? sorry. I don't actually know how much of what I'm talking about you've read.
15:14 < gmaxwell> I didn't want to repeat it all if you've read it all.
15:14 < amiller> i've at least skimmed both threads but i am pretty sure i don't understand many details correctly
15:15 < gmaxwell> amiller: the idea is that to redeem the prize in our chess game you either present proof you've seen  a complete transcript for the game in which you've won OR
15:16 < gmaxwell> if the time is past a timeout, AND you present a transcript where your move is last then you can spend it with a transaction whos TXOUT is constrained, such that:
15:16 < gmaxwell> it can be spent after a final timeout (some time from now)  OR   it can be spent by a similar constrained transaction which a somewhat advanced final timeout and proof of a witness of a longer transcript.
15:17 < amiller> witness of a longer transcript than what
15:17 < gmaxwell> that the longest seen so far, it accumulates.
15:17 < amiller> here's an edge case though
15:17 < amiller> suppose player 1 has a timeout
15:17 < amiller> but player 2 does *not* have a timeout
15:18 < amiller> player 1 publishes his move in time
15:18 < amiller> player 2 pretends that he didn't see the first move, and shows a long transcript and tries to redeem the timeout
15:18 < gmaxwell> He can't, because player 2 can't produce a longer transcript on his own.
15:19 < amiller> player 1 can't just try to timeout player 2 because player 2 isn't on the clock, but you would want to prevent player 2 from omitting the published move
15:20 < gmaxwell> amiller: e.g. player 1 moves, player 2 tries to redeem an empty transcript. Player 1 says fuck you and publishes a 1 move transcript. Player 2 can either give up, or present a 2 move transcript. If he does the latter player 1 can present a three move transcript and so on.
15:20 < amiller> when is the coin irrevocably spent?
15:20 < amiller> if this can keep going on
15:21 < gmaxwell> when the transcript can grow no more, or when someone finally misses an update timeout.
15:22 < gmaxwell> and sure, it's probably possible in chess (it is possible in go) to setup a case where the game goes periodic-stalemate in which case it could go on forever if no party will yield. But the evaluation model doesn't matter there.
15:23 < gmaxwell> (e.g. you can't solve this by having proof of publication)
15:52 < jtimon> gmaxwell, for your non-disclousure key logic problem
15:54 < jtimon> any boolean ecuation can be turned into the form (a * c * e) + (b * c * e), wait
15:54 < jtimon> let me look at your example
15:54 < jtimon> well, no
15:55 < gmaxwell> the 2 of 3 can be expanded into (a&&b or b&&c or a&&c)
15:55 < jtimon> the point is to build a tree with N or branches
15:55 < jtimon> n OR branches
15:56 < jtimon> a tree in which width is OR and deep is AND
15:56 < jtimon> argh
15:56 < jtimon> words don't come easy
15:58 < jtimon> and anything can be expanded to that structure
15:59 < jtimon> to get the coins you only need to reveal the relevant branch
15:59 < jtimon> sorry, I'll smoke a cigarrete while trying to translate that to english
16:01 < gmaxwell> jtimon: right, but because hiding a branch still costs you a 256 bit hash, it doesn't save you anything to hide a branch that only contains one key, its better to just test it directly at the current level.
16:02 < gmaxwell> e.g. you would not represent   a or b    as   a else {b}
16:07 < jtimon> ?I don't understand the e.g.
16:08 < jtimon> but about the hidden branch hash cost
16:08 < jtimon> it is on the scriptSig, not the scriptPubKey, does it really matter?
16:08 < jtimon> well, yes, sorry
16:08 < jtimon> not that much, but still matters
16:18 < jtimon> <maaku_> it fails spectacularly at managing DoS potential with its TC scripts
16:18 < jtimon> I'm not so sure about that
16:19 < jtimon> my understanding (and I'm not sure I understand the proposal)
16:19 < maaku_> jtimon: iirc his proposal is to have script execution paid for in fees
16:19 < jtimon> is that it is protected through fees
16:19 < jtimon> yes
16:19 < maaku_> but if the script is invalidated by running too long, then how does the miner collect the fees?
16:19 < maaku_> *transaction is invalided by the script running too long
16:20 < jtimon>  you're paying fees as it is executed, so the execution is somehow "in-chain"
16:20 < jtimon> maybe the scripts are executed in several blocks
16:20 < jtimon> and only a max instructions per block is executed
16:20 < maaku_> then how do you reach consensus on it?
16:21 < jtimon> that was my thought at the time, but doesn't look very scalable
16:21 < maaku_> you bloat the chain with invalid transactions that steal a little bit of fees from its inputs nonetheless?
16:21 < jtimon> because everyone executes the number of transactions that can be paid or the max_per_block (if there's any)
16:22 < jtimon> as said, it doesn't look very scalable at a first glance
16:22 < gmaxwell> maaku_: they move the execution construct out of the transaction and make it free standing.
16:22 < jtimon> I guess he has solved TC by fees in a non-scalable way
16:23 < gmaxwell> e.g. you have an object that has a balance which it can use to pay for execution.
16:23 < gmaxwell> it stops executing when its balance is 0.
16:23 < gmaxwell> it create it at all requires positive fees.
16:23 < maaku_> so it's a distributed-replicated time-share system?
16:23 < gmaxwell> this isn't to say that any of its is good or makes any sense.
16:24 < gmaxwell> the fees are paying the wrong people... unless you convert mining to be a proof of agent execution. :P
16:24 < jtimon> and I hadn't even considered problems related to script-consensus
16:25 < jtimon> exactly miners will get fees, but the rest of validators will be screwed for nothing
16:25 < jtimon> is that what you're saying gmaxwell?
16:25 < gmaxwell> yes.
16:27 < jtimon> so let's go back to compressed scripts
16:28 < jtimon> you could have a list of addresses Lk
16:28 < jtimon> scriptPubKey only contains it's hash
16:29 < jtimon> with a byte or a short, you can select the order in which the scripts in Lk will appear
16:30 < jtimon> the Lk is 64 bit per variable
16:31 < jtimon> then you can have a list of lists OR_list
16:32 < jtimon> each of the lists is named AND_list_n
16:33 < jtimon> and you have another byte to select n
16:33 < jtimon> scriptPubKey contains a hash of Or_list + Lk
16:34 < jtimon> the AND list just contains bytes reffering to scripts in Lk
16:34 < jtimon> indexing
16:35 < jtimon> so the public keys can be presented in any order selected by order_byte
16:35 < jtimon> of the list Lk
16:36 < jtimon> to sign the AND list selected by logic_byte
16:38 < jtimon> there's plenty of redundancy to optimize here, I'm just using bytes for convenience
16:39 < jtimon> not redundancy, unused bits
16:40 < jtimon> well, I'll think more about this until I can express it in a way that can make sense or that helps me find the deficiency by myself
22:09 < jgarzik> bitcoin's scripts are "written in a programming language called Script"
22:09 < jgarzik> http://theumlaut.com/2014/01/08/bitcoin-internet-of-money/
22:10 < jgarzik> pretty good article though
22:32 < Luke-Jr> jgarzik: I'd concur with that statement.. :P
23:53 < maaku_> jgarzik: if that's the grossest error they made, i'd say that's doing pretty well :)
23:59 < phantomcircuit> lol
--- Log closed Fri Jan 10 00:00:20 2014