00:12:53gmaxwell:andytoshi: why are there no good explinations of DSA and schnorr on the web? this was just on reddit http://www.reddit.com/r/Bitcoin/comments/2j8lrr/the_math_behind_bitcoin/ and like all the other ones I've seen it walks through the mechanical procedure without actually giving much insight into why any of it works.
00:21:11tacotime:Did anyone review AnonCoin's improvement to Sander's RSA UFO paper?
00:21:47gmaxwell:I think I saw that before and it made no sense. Is that the thing where it's "multiple small UFO" ?
00:22:01tacotime:Yeah it looks like it
00:22:09gmaxwell:I was excited when I heard the ideas and the numbers I came up with were not improvements.
00:22:50gmaxwell:they also distributed some totally pointless and sketchy number mining code which did nothing particularly useful except waste cpu cycles (in python, no less)
00:24:27gmaxwell:I'm not sure how interesting it would be even if it did work, the zerocoin proofs are huge and slow even with a non-trapdoorless number which is the smallest it can be.
00:25:14gmaxwell:loading that page, the security argument they give there is somewhat bogus.
00:25:24gmaxwell:it's like the NIST argument that the NIST curves are 'random'.
00:26:10gmaxwell:Using a sha256 output you can grind is not nothing up your sleeve. For example, they could have a fast factoring farm running, and then grind numbers until they get a set that they can factor completely.
00:26:30tacotime:Yeah they say average verification time is 0.5 s with proofs 128 kb... since the entire AnonCoin network is run over I2P and Tor, you'd thing that (a) you'd be very very easily able to ddos the network by spamming ZeroCoin tx and (b) that you'll probably take down those distributed networks because they're not designed to scale to huge quantities of data like that.
00:27:27tacotime:Proofs are also stored off chain
00:27:34tacotime:Which is a whole separate issue in and of itself
00:27:52gmaxwell:0have they actually implemented it? 0.5 is suspicious, libzerocoin is that slow and it doesn't have to use a bunch of seperate accumulators or over-sized numbers.
00:28:05gmaxwell:it should be several times slower than libzerocoin.
00:28:30tacotime:They're saying they did, I guess we'll find out when they publish their code tomorrow.
01:33:17CryptOprah_:CryptOprah_ is now known as CryptOprah
01:43:04SomeoneWeird_:SomeoneWeird_ is now known as SomeoneWeird
01:43:34SomeoneWeird:SomeoneWeird is now known as Guest83486
01:48:06amiller:i think i finally have a good way of organizing all the interesting bitcoin proposals/ideas for my systematization of knowledge paper
01:48:09Guest83486:Guest83486 is now known as SomeoneWeird
01:49:26amiller:1. blockchain consensus strategies, which includes PoS, PoW of all forms, and as an extreme/illustrative case, single signer or quorum signer ledgers like LaurieCoin (what I call ben laurie's paper) and even ripple
01:49:53amiller:also here i would include all the options for doing SPV proofs, like the hash highway skiplist and also using snarks for spv proofs
01:50:35amiller:the main things that aren't relevant here are anything about what kind of transactions are supported or anything about protocols built on top of it
01:50:53amiller:2. validation rules and algorithms for checking/proving that rules are followed
01:51:29amiller:rules include the bitcoin scripts, proposed new opcodes, things like zerocoin/zerocash which involve basically new transaction types
01:52:12execut3:execut3 is now known as shesek
01:52:33amiller:extreme examples are ethereum which has extremely expressive validation rules that let you store arbitrary state and do arbitrary computations, and a hypothetical "DataOnlyCoin" that has no currency layer, it's just a blockchain where you vote on new data to include
01:52:52amiller:as for ways of enforcing validation rules,
01:53:41amiller:there's the bitcoin "store everything" approach, the committed-UTXOset scheme where you don't have to store everything to verify, the Merkle Mountain Range scheme where you also don't have to store everything to verify things but you also don't have to store/receive very much in order to make proofs
01:53:58amiller:and a hypothetical SnarkCoin where verification of everything is O(1)
01:55:01amiller:3. protocols built using bitcoin (or something closely related) as a component
01:55:59amiller:the main way to break things down here are the models and trust assumptions involved
01:56:39amiller:a) two or multiparty protocols with minimal trust, like the microcontracts gradual release protocol, the lottery game
01:57:06amiller:b) semi-trusted server model where a third party has to be 'available' but is constrained in some other way, like proof-of-existence
01:57:24amiller:c) "trust-but-verify" sort of auditable protocols like green addresses
01:57:27kanzure:would be nice to have a more specific metric for trust measurement, or even proposing some function even if you don't want to work out the details
01:57:39amiller:where a third party can temporarily break something but the blockchain can be used to provide evidence
01:57:48amiller:also all the "fraud proof" sort of ideas go in here
01:58:18amiller:i think colored coins and mastercoin in their typical use case go here
01:58:42amiller:where you have to rely on a server to tell you about the current state of things, because computing it from scratch is expensive, but if someone does compute it from scratch it's possible to show where they faulted
02:00:12amiller:there are others i can't really be exhaustive here... in general protocols for these different kinds of models are incomparable because they have different kinds of parties/assumptions, but it's meaningful to talk about the cost (computational/storage/network) for both parties as well as the cost (computation/storage/network) imposed on the bitcoin network, which should basically correspond to fees
02:01:31amiller:okay, that's all. i think almost every interesting idea we've seen can be placed in one of those categories and compared meaningfully with the others things in those categories
02:02:17kanzure:maybe there can be a "cost of trust" measurement. hm.
02:22:52petertodd:amiller: there's a middle ground between "bitcoin verification" and "dataonlycoin" where you verify script execution, but don't actually have a (U)TXO set
02:23:40amiller:i guess that's possible..... a) what good is it? b) anything really interesting about it? c) has anyone actually asked for that?
02:24:55petertodd:amiller: well, it could make proofs for a treechain-type system much more compact, as the script being executed could be "check the last x blocks for double spends, fail if one found", where x is the age of the previous output
02:25:56petertodd:amiller: equally it'd make SPV proofs in general more compact - check that the hash of the script and its execution result exists in the block rather than see the script itself - also good for upgrading rules
02:26:02nuke_:nuke_ is now known as nuke1989
02:26:53petertodd:amiller: all fairly weak use-cases, but worth mentioning for completeness
02:27:11amiller:i think completeness isn't really a goal
02:27:36petertodd:amiller: well, how you define 'systematization' is up to you :)
02:28:06amiller:i think the goal is to a) come up with evaluation metrics and categorizations that *could* be complete, so if you came up with something that was plausible and really broke or cut across the organization i laid out then that would be good
02:28:42amiller:b) to include the most interesting or important (admittedly subjective) ideas and fit them in
02:29:18petertodd:amiller: well, in that case leave it out
02:29:55amiller:it's a cool idea though now i'm still thinking about it
02:30:40amiller:you could have ehteruem without the data store
02:32:25petertodd:amiller: re: colored coins, I'm working on a intermediate solution where you pass around tx path proofs, and then have the issuer (or potentially another TTP) periodically shorten those proofs by updating the color definitions to include all colored txouts in a merkelized binary prefix tree. advantage there is the trusted part can be kept off line and easily checked, and the online servers are purely for convenience, indeed, with payment ...
02:32:31petertodd:... protocols they aren't necessarily even needed
02:33:05amiller:yeah i think that makes sense
02:34:07amiller:people have been designing contract/fairness/etc protocols for dozens of years involving combinations of trusted third parties + optimistic/auditable third parties that get caught if they deviate, and all kinds of possible efficiency/security tradeoffs
02:34:22amiller:so it's pretty cool to add in "blockchain" as another kind of component to add to these
02:34:57petertodd:yup, this is an interesting case where other than the issuer there aren't any trusted third parties, although periodic maintenance is required on the part of the issuer for efficiency
02:36:29petertodd:where would hub-and-spoke micropayments fit in this systematization?
02:37:13amiller:in 3.something somewhere... i'm a little hazier on how many "different" models there are
02:37:54amiller:it's sort of halfway between semi-trusted (for availability if not everything else) and the gradual release two party gcase
02:38:00kanzure:forcing categories might be wrong anyway
02:38:43amiller:kanzure, yeah if the categories are forced then i've done a bad job, if they feel forced it's a sign i should try some other way of cutting across them,
02:38:44petertodd:amiller: yeah, it's not a fundemental type of model
02:39:22amiller:on the other hand what i'm really looking to accomplish here is to find useful ways of slicing and dicing these things that make it easier for people to understand and to group these things, and especially to compare/contrast/evaluate them
02:40:10amiller:it's fuzzier than the theory stuff i normally like to do, but it's also not "non falsifiable", i can try to have a high standard and admit failure, try again, etc
02:40:51amiller:i feel like there are some basic principles for building protocols that use blockchains (and other things) like amortization and safety in numbers
02:42:33petertodd:for your consensus strategies, you should point out that incentive to do PoW may include non-monetary, as well as mixed systems with multiple contributors
02:42:54petertodd:(or equally, generalize!)
02:42:57moa:amiller: i'd be interested to see how you do that, it seems like a useful starting point ... always have issues explaining to 'outsiders' the subtle differences between the trust models and trade-offs re computational resources
02:43:03amiller:i don't know where to put merged mining
02:43:10amiller:that's one of the edge cases i really don't know where to put
02:43:20kanzure:why are you bothering with categories anyway?
02:43:21petertodd:amiller: yeah, merge-mining is really odd... asymetric is the word that comes to mind
02:43:32amiller:i don't think it's asymmetric you could have mutually merge mined currencies
02:43:53petertodd:amiller: even in that case for a given attacker the costs are asymmetric
02:44:15petertodd:amiller: maybe a better word is non-uniform
02:44:26amiller:i think i will deal with merge mining in a separate paragraph because there are a lot of things to say about it
02:44:27kanzure:instead of categories you can just call it a work of observational cryptography
02:44:56amiller:kanzure, that seems fuzzy and unprincipled, i don't know how i can be rigorous without some approach like this
02:45:22amiller:you might be right though, i don't really know what i'm doing here and am trying to make it up as i go along (including getting feedback from academics and bitcoin folks alike on what might help)
02:45:33kanzure:where rigor is "adequately predicting future models that improve on current implementations" ?
02:45:45petertodd:amiller: you can also mention pseudo approaches like sidechains which can have OK security assuming sybil attacks are weak/non-existant via reorg proofs
02:46:04petertodd:amiller: (remember that all this PoW stuff does is resist sybil attacks!)
02:46:06amiller:hrm, that would be a good kind of rigor. but i don't see how i can use that currently to validate this
02:46:12moa:the miller 'trust' number sounds good ....
02:46:25amiller:i don't think trust as a 'number' function makes much sense
02:46:43amiller:that's a response more to kanzure's earlier statements than moa's line :p
02:46:52moa:non-dimensionalised trust
02:46:59kanzure:well it has to be something, even though not a number
02:47:06kanzure:(otherwise it's not worth discussing)
02:47:33amiller:i want to think i'm being more rigorous here than other intro-to-bitcoin or list-of-everything-about-bitcoin guides but i'm not really sure how to check i'm actually doing that.
02:47:44petertodd:moa: I like assigning trust a number equal to how many people can break that trust - hundreds in the CA cert system, a tiny fraction in the Bitcoin system (er... modulo that ghash.io problem...)
02:48:01moa:qualitatively it appears there is a 'spectrum' of trust
02:48:10petertodd:moa: thus systems with a high k-trust are the weakest and most reliant on it
02:48:30amiller:so what else can be used to determine whether a way of breaking down ideas.... one good way is that ideas in a category should be comparable to each other in some quantifiable dimensions
02:48:35kanzure:amiller: what about, "readers walk away with dramatically improved tools to work in this space"?
02:48:59amiller:if i try to build a comparison table and i end up with most of the columns 'N/A' then that's kind of a failure
02:50:40petertodd:amiller: don't forget to include a column labeled "sum total of bribes received from schemes pumpers"
02:50:50kanzure:amiller: what about a sort of rigor focused on listing known attacks on slightly weaker implementations/proposals
02:51:10kanzure:(or even those current implementations)
02:51:11petertodd:amiller: send me your address and I'll send you $5 for treechains
02:51:20amiller:petertodd, one thing i'm doing is trying to avoid discussing 'altcoins' as opposed to the sort of abstracted concepts/ideas
02:51:29amiller:any given altcoin generally implements a dozen kinds of changes
02:51:37moa:petertodd: that would be like a percentage of participants that have to act against their long term interests for the system to break ... i.e. 51% for bitcoin and 1 out # of users for centalised client-server
02:51:59amiller:petertodd, that's hilarious, i should publish a draft of this with a bunch of empty rows in tables... and put little real estate auction price tags on them all
02:52:04petertodd:amiller: yeah, what is or isn't an 'altcoin' is at one level just a matter of who is a market leader at any one time anyway - the hatred of altcoins around some parts always seemed kinda cowardly to me...
02:52:16petertodd:amiller: oh, that's brilliant!
02:52:28amiller:sergio lerner gave me a big pull request full of explanations of every single one of his altcoins
02:52:42petertodd:good riddance..
02:52:42NewLiberty:hatred and fear are cousins. The only thing that can really kill bitcoin is a better bitcoin
02:52:55amiller:he has this style of developing a couple of well reasoned parameter changes, at least one novel idea, and packaging those all up with a completely different name
02:53:05kanzure:petertodd: that hatred is probably just because nobody has time to sit around debunking everything and proposing attacks.
02:53:25amiller:that style is ok i guess but it makes it way hard to separate out the meaningful parts
02:53:27petertodd:NewLiberty: yeah, I realized not that long ago that currently I actually have an incentive to see Bitcoin fail due to a blocksize limit removal :/
02:53:48petertodd:amiller: have any had any success?
02:53:49amiller:petertodd, you're required by professional ethics to turn in all your coins to jeff to hold in escrow
02:54:07petertodd:amiller: sorry, I blew it all on hookers and blow in vegas last week
02:54:40petertodd:amiller: (actually crack due to the low price...)
02:54:48moa:poker face
02:55:03amiller:i don't know where to fit in merge mining so far, i also don't know how to fit in other kinds of cross chain transactions
02:55:26NewLiberty:petertodd, good point. a worse bitcoin could also kill it, if folks follow an unfortunate fork
02:55:34amiller:i think it fits sort of naturally enough in this protocols-on-top-of section because another blockchain can just be a party in a sense
02:55:49amiller:side chains can have two pow chains that validate SPV proofs about each other
02:55:59petertodd:amiller: a tricky thing with cross-chain transations is they can be at one level just a cool protocol, and at another level, they can form the basis for a complete scalable system
02:56:18amiller:petertodd, okay so that's a good question to analyze
02:56:26amiller:what's the basis for a complete scalable system
02:56:32moa:cross-chain multi-sig payment channels?
02:56:33petertodd:amiller: so ok, you have a measure of how the security of a given scheme degrades as it scales
02:56:35amiller:and does it still follow the basic structure of pow-consensus blockchain
02:57:33petertodd:amiller: for instance "just a bunch of altcoins" has a fixed security level as it scales up in the best case, and probably worse in practice as splitting all tha thashing power across n chains implies 51% attacks can be arranged easily due to availability of hashing power
02:57:51petertodd:amiller: sidechains is like that too, but MM-sidechains potentially even worse because attacks are free
02:57:55NewLiberty:so merge mining
02:58:24NewLiberty:<-- types to slowly in my old age
02:58:42amiller:NewLiberty, that's fine you're just on the 0.25 -wizards tree chain
02:59:03amiller:the attacks-free part of MM is because of merge mining and not unique to the side chain part at all
02:59:33amiller:just a bunch of alt coins scaling up whatever is just as applicable to a bunch of altcoins
02:59:34jtimon:plus is false, there's an opportunity cost
02:59:45amiller:i dont see how this involves the "side chains" part of side chains at all
03:00:09jtimon:and only miners can do it, otherwise petertodd would have proven his point by attacking namecoin for free long ago
03:00:12petertodd:amiller: true, so ok, we can strengthen that statement: MM-sidechains is even worse than MM as the pegs means attacks have strong incentives to perform as you can steal the coins in the peg if done right
03:00:41petertodd:amiller: which gets back to my earlier point re: how secure are systems against sybil attacks
03:00:52petertodd:amiller: and that in turn applies to fraud proof schemes too!
03:01:06amiller:there's in general a ciruclarity i have to cut somewhere
03:01:20amiller:i have plenty of text (from coauthors) about consensus properties and the incentives that lead to them
03:01:42amiller:so i have to say, all of these proposals about different consensus strategies are about different ways of achieving the same kind of basic goals
03:01:45petertodd:amiller: is this circularity, or a n-dimensional solution space?
03:01:54amiller:* amiller mind explodes
03:02:13amiller:i have a wedge which involves to one side, the consensus properties are a goal,
03:02:19amiller:and to the other side, the consensus properties are an assumption
03:02:21petertodd:I mean, seriously, you can tweak the knobs one way or another, trading off various things for more or less sybil attack resistance for instance
03:02:34amiller:but it's true that any change to the merge mining, to the validation rule set, to the economic things that are permitted etc
03:02:50petertodd:remember my thought experience of "broadcast coin" where you simply broadcast your transactions and rely on you not being sybil attacked
03:02:51amiller:can cause the incentives to break down that are used to justify the assumptions upon which we build the applications anyway
03:03:18amiller:i don't have "sybil attack resistance" as a first class concept in my current schema
03:03:28petertodd:I think you absolutely have to
03:03:32amiller:try talking me into it and i'll see if i feel like it.
03:03:41kanzure:sybil attack resistance is just "treat everyone as an adversary" or "don't assume that identity is extremely expensive or meaningful"
03:03:45amiller:i have something i think you'd recognize as proof of publication
03:04:03petertodd:so, do you agree that if sybil attacks weren't an issue, you'd just broadcast transactions?
03:04:08petertodd:amiller: ?
03:04:15amiller:my wedge is consensus goals: a) nodes eventually/rapidly agree on a history of transactions, b) anyone can insert (valid) transactions and they're included in a timely fashion
03:04:22kanzure:what sort of sybil are we talking about here.. p2p nodes?
03:04:44amiller:to even call it sybil i need to assume something like 1 transcation per 1 node or something
03:04:44petertodd:kanzure: could come in multiple forms!
03:05:05amiller:i think what you mean then generally is resource exhaustion, and it's "sybil" just in the sense that if there's enough resources for everyone to use them fairyl, one asshole can use them all up
03:05:25petertodd:with PoW systems sybil is defined very strangely, as you make a 51% assumption, and then the retargetting rules make the size of the attacker that you can defend against fall over time
03:06:14amiller:what i want is a nice sequence that everyone/suffiiciently many people agree on so i can call it "the history"..... i am willing to make some assumptions (e.g. 51%) to get there, and the protocol (poW) has to get me the rest of the way
03:07:57petertodd:so maybe then the form of sybil attack resistance is really about how you define the scope of the consensus that comes to consensus about 'the history'
03:08:39amiller:well.... okay this is an interesting point but i think my current schema is okay....
03:08:42petertodd:51% PoW says that the parties forming that consensus are defined by hashing power, and once you learn of some amount of hashing done, the minimum attacker size starts off at 51% and drops over time due to retargetting rules
03:09:06amiller:for the purpose of evaluation of all the things i mentioned, quantitiatively i usually look at costs as a function of the number of items that have gone through the log N
03:09:14amiller:so N transactions or whatever
03:09:27petertodd:MM PoW is like that, except that the cost to *join* that consensus is zero - non-MM PoW has a cost of joining
03:09:54petertodd:hmm, I'm not sure I'd talk about it in terms of 'n transactions', but maybe that makes sense
03:10:16petertodd:so Ripple consensus is local, the cost to join is zero... but membership is defined by who trusts you
03:11:16petertodd:and a 2-way pegged currency with MM PoW still has that zero cost to join the consensus, but it *also* has a potentially high reward to acting maliciously - steal all the coins - which is available if you have sufficient hashing power
03:12:06petertodd:(plain old PoW kinda has similar rewards, but in practice acting maliciously is hard to profit from - doubly so if multiple disparent uses contribute to the same PoW security)
03:12:16amiller:okay good this is the stuff from you that i wanted to see if my schema could withstand.
03:12:22amiller:so in my extreme simplifeid rule set
03:12:29amiller:i'm still assuming that consensus means "publishing"
03:12:41amiller:yet there are no direct incentives to actually look at the data
03:12:45petertodd:yeah, publishing something - zero-knowledge consensus isn't a thing AFAIK
03:12:51amiller:you can save cost by not fetching it and your peers can save cost by not sending it
03:13:06petertodd:right, OTOH your peers have (weak) incentives to catch you doing that in many schemes
03:13:08amiller:my usual answer is the storage puzzle helps a bit but i'm not confident about that
03:13:32amiller:yeah i guess it's on one of those edge cases about credible threats and hiddne knowledge about whether the other player is actually lying in wait or not
03:13:59petertodd:so treechains makes that situation really weird, because the problem with miners not actually publishing data is purely when you try to actually use the system - it's still perfectly secure
03:14:29amiller:i guess, i don't see how you actually get around that sort of reasoning
03:14:30petertodd:(and actually, s/treechains/generic data-publishing-only chains/)
03:14:44petertodd:amiller: ?
03:15:20amiller:this sucks because this literally is the edge case where i think my basic underlying assumptions break down, but i don't think i can write clearly or organize anyone else's thoughts (basically just yours) here.
03:15:33amiller:but, i totally believe it's possible that by figuring this area out we'd end up with a better system and a more interesting area
03:15:46petertodd:you mean with respect to this notion of enforcing publication?
03:15:49amiller:my basic underlying assumption is that the consensus mechanisms are all based on every node *seeing* all the data included in the chain they're voting on
03:15:57petertodd:so remember my 'disentangling mining' paper
03:15:58amiller:so there's a notion of "the history" and "all the nodes"
03:16:13amiller:yes i "remember" it but not understand it
03:16:30petertodd:so the idea there re: consensus is that you have a consensus domain - who needs to be in consensus for a given txout's spentness - and the size of that domain is at minimum just the payee and payor
03:16:31kanzure:sometimes nodes get kicked out of the consesus set, so there are different histories (especially in hard fork scenarios)
03:17:07petertodd:that's why if participants cheat and don't actually publish as they are supposed the system is still secure in the sense that you can't double spend, but it's also useless in the sense that you can't prove you haven't double-spent
03:17:12amiller:so i don't know how many consensus sets there are or who's in them.... but within a consensus set the goal is to have everyone have seen everything.
03:17:50petertodd:now if you have a *single* miner give you the *single* bit of data you need to prove you haven't double spent, *you're* fine even if no-one else in the world has that data. (well, that and the person you send the funds too)
03:18:32amiller:i'm lost about what that means
03:18:48amiller:it's not precise enough to get through syntactically and my intuition is lost at this point when we're talking about "consensus sets"
03:19:06kanzure:no, use petertodd's consensus domain idea instead
03:19:19amiller:s/consensus set/consensus domain/
03:19:19petertodd:ok, so we have a scheme where I have to prove to you that the coins I'm giving you were first spent in the transaction I'm giving you right now
03:19:20gmaxwell:petertodd: So the cost of attacking bitcoin is free?
03:19:36kanzure:gmaxwell: unsuccessfully? probably?
03:19:51petertodd:amiller: that proof is that in some time period no other spend was published, then one was published, the transaction I'm giving you
03:20:05gmaxwell:(I think you need to clarify your position some, because as stated it has crazy conclusions like that... after all, the relationship is symmetric, bitcoin is mm as much as namecoin is mm)
03:20:09kanzure:anyone can delete their blockchain on their computer, is that an attack..
03:20:23kanzure:although you may be talking about attacking the bitcoin network instead. oops.
03:20:28petertodd:amiller: those publications get committed to via block headers in some scheme - critical thing is the *contents* of those publications don't need to be known to anyone in the world but you and I
03:20:38amiller:petertodd, i don't know what you mean by "publish" here now that we are talking about consensus domains rather than a simple case of "all the nodes" and one history
03:20:42petertodd:gmaxwell: ?
03:21:15petertodd:amiller: think of publishing as the first step in the process by which you establish consensus about what history is
03:22:29petertodd:amiller: now, imagine we have a set of history books, each with an index for various topics, if I want to prove to you that no English king was alive from 1950 to now, I can give you the contents of the parts of those books indexed under "English Kings, 1950, 1951, 1952.. etc."
03:22:44gmaxwell:petertodd: above commentary on MM making attacks free. I'm pointing out that you're missing details, because the MM relationship is symmetric. E.g. Bitcoin has been a merged mined system ever since namecoin switched to merged mining.
03:23:00amiller:petertodd, you need to go back and help me constrain what you mean by "consensus domains"
03:23:16gmaxwell:So that argument needs to be narrowed some or it's-- in effect-- saying attacking Bitcoin is free because namecoin exists. :)
03:24:10petertodd:amiller: so consensus domain is the notion of who needs to actually have consensus about the *contents* of some part of history, IE, whether or not a given txout is spent or not - in the Bitcoin system everyone who wants to mine and fully verify needs to know, because blocks can be invalid if the rules aren't followed
03:24:20kanzure:amiller: re "all the nodes and one history", there has never really been just one history (even the blockchain itself can have missing parts of history, by which i mean, things that were never mined)
03:24:50petertodd:gmaxwell: that's a really useless argument - that symmetry is bogus from an economic point of view - from the point of view of a given attacker it's more likely than not that their incentives will be asymmetric
03:24:50amiller:kanzure, things that were never mine, i have a nice grasp of "the history" meaning some growing prefix of the blockchain that we all agree on
03:25:19gmaxwell:petertodd: I'm not making an argument, just pointing out that what you were saying was insufficiently tight.
03:25:20petertodd:amiller: oh, and "growing prefix" is good here: remember that there's a distinction between the commitment of that prefix, and the contents of that prefix itself
03:25:54amiller:petertodd, i don't know what you mean by "needs to have consensus" about some contents or how that's determined, like is it determined in advance, is it apparent to everyone where they need to know about etc
03:26:00petertodd:gmaxwell: sorry, you're about the 20th time I've had someone try to argue with me on merge mining this past week...
03:26:26petertodd:amiller: so you see how in Bitcoin you actually need to know the contents of blocks if you are going to participate fully?
03:26:37amiller:petertodd, that seems application specific and i was really hoping for a nice way of chopping the circularity somewhere convenient
03:26:45amiller:petertodd, yes i see that part
03:26:46gmaxwell:petertodd: hm? you started talking above and said something which is not pedantically correct, and is perhaps quite misleading to someone who doesn't understand these things as well as we do.
03:26:52kanzure:amiller: wlel, it's certainly not determined prior to connection (except for high-level forks running on other ports anyway)
03:26:59petertodd:gmaxwell: that's an apology :)
03:27:23petertodd:amiller: now, if Bitcoin didn't have block validity rules, you could freely mine without actualy knowing what was in any given block
03:27:36amiller:i hereby apologize in advance, for everything
03:27:52petertodd:amiller: fuck you and die in a fire, your mother was an elderberry
03:28:02kanzure:me next
03:28:14amiller:petertodd, no i don't agree with that
03:28:20petertodd:kanzure: fuck you, your name sounds like a particularly bad operating system
03:28:37petertodd:amiller: well, in the sense that the blocks you produced would be "valid" blocks
03:28:45amiller:you can generally "safely" mine already without validating anything
03:28:51amiller:that's not necessarily true either
03:28:55petertodd:amiller: yeah... and that's a flaw :)
03:28:55amiller:evne wihtout knowing the contents...
03:29:02amiller:you could potentially need to reveal the contents
03:29:15amiller:i can make a false commitment to some untyped data that i still am unable to reveal
03:29:24kanzure:you don't need to validate transactions but you are mining based on history still, aren't you
03:29:27kanzure:does that count as validating
03:30:17petertodd:ok, so the model you'd use for the "non-validating-blockchain" is I'd have to prove to you have some coin history was valid - for the bitcoin blockchain as there's no index, that proof needs to be the whole blockchain after the coins were created
03:31:02amiller:uh let me just clarify some words there for the next few lines because i think this is a useful idea but some of those were misleading phrases
03:31:02moa:what's bugging right now is all the "bitcoin blockchain is a global ledger technology that could very useful for payments" when fact is that the blockchain is a journal of past transactions and the global ledger is actually UTXO ... they could at least get the terminology/understanding correct before they discuss adopting the latest gee whiz tech.
03:31:06petertodd:if you slightly constraine the rules so that miners have to mine blocks with valid indexes of some kind, then that proof can be smaller - just the parts of the blocks matching some index (or proof nothing matches)
03:31:27petertodd:amiller: go
03:31:28amiller:i think we're about to talk about a blockchain with no validation rules, just untyepd unregulated data packets in the transactions
03:31:35petertodd:amiller: right
03:31:36amiller:i'd call that a "no transaction rules" blockchain
03:31:45amiller:yeah and that implies no index
03:31:52amiller:okay what do you mean by prove and coin history thouhg
03:32:28petertodd:amiller: well, so if miners don't validate, Bitcoin itself would still "work" in the sense that I can give you the whole blockchain and say "here's proof! (other than all the irrelevant junk)"
03:32:36gmaxwell:petertodd: I think there is a middle ground where the blockchain is only a anti-replay oracle but has no other rules.
03:32:46gmaxwell:(er there is a middle ground which is _very_ interesting)
03:33:11gmaxwell:Because it lets you work with completely hash-compressed and encrypted data.
03:33:49petertodd:gmaxwell: right, and actually that's a more interesting middleground than my example above re: script-verification-only chains
03:34:20petertodd:gmaxwell: (granted, anti-replay needs authentication... so maybe that does encompase it?)
03:34:44amiller:petertodd, okay i think i follow what you're saying, that's not the "only" option because you could also have useful protocols with some other trusted parties, like servers in mastercoin for example (which only make use of bitcoin as a log like this)
03:35:02gmaxwell:I've come up with some pretty neat designs based on the idea of a system that does _only_ anti-replay. You can use very narrow authentication though. like preventing replay of a public key.
03:35:24petertodd:amiller: yeah, and once you accept that works, you "just" need to optimize it until it's practical :)
03:36:27petertodd:gmaxwell: actually, come to think of it, I think that's roughly what I was talking about by "TxIn set commitments": http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg03307.html
03:37:34gmaxwell:RT MM secutiy I'd suggest something like "the cost of attacking is the oppturnity value of
03:37:37gmaxwell:not attacking, blockchains with low income for miners are not secure." ...
03:37:41gmaxwell:I think this is actually the key point, not sure if MM actually really
03:37:43gmaxwell:matters other than it can make the hashrate deceptive.
03:37:46gmaxwell:E.g. In the worst case namecoin arguably only has 50+episilon NMC/block security, even though
03:37:49gmaxwell:the difficulty is 90% of bitcoin's. There is probably some miner altriusm
03:37:52gmaxwell:term that ought to be included there.
03:38:00gmaxwell:er WRT instead of RT there.
03:38:05petertodd:gmaxwell: makes sense
03:38:07amiller:petertodd, okay now what i don't remember what you were trying to get to, but we're now pretty clear on whats the "no rules" blockchain and one way of using it
03:38:36amiller:you're trying to talk me into dropping "everyone sees all the data" as a basic common goal/assumption in blockchain sstems
03:39:19petertodd:amiller: heh, ok, so with regard to publication - in the "no rules" blockchain, the only people who care about the actual contents of blocks are the people who want to actually use the system to make provable statements - in principle if miners didn't distribute blocks to *each other* the whole thing would work fine, so long as somehow block contents go to people actually using the systrem
03:39:34petertodd:amiller: heh, of course I am, "everyone sees all the data" is obviously unscalable
03:39:48gmaxwell:amiller: one argument I gave a while back is that in the limit the privacy and communications efficiency are equal. You can imagine some blockchain where no one sees anything they're not party to (except perhaps commitments), ... and they all give each other O(1) snark proofs that everything is valid.
03:40:37petertodd:amiller: basically you can have more scalable consensus about history involving more participants if those participants don't actually have to know the contents of that history
03:40:56amiller:gmaxwell, but there's no there there... i don't see how it's useful to make a snark proof about something without getting to assume that someone/everyone else has seen the original
03:41:31amiller:i don't get liveness in the sense that "the nodes" can't build on top of that history if they don't "have" it
03:42:13petertodd:amiller: you see, this is a practical problem: in PoW consensus anyone can record something down in the history log (subject to the rules of the system), so you want to incentivse anyone doing so to publish the contents of those logs so that users can actually get them and make useful proofs
03:42:14amiller:maybe what you're going to say next is, whoever cares about it has to have it
03:42:15kanzure:non-miners aren't building on top of history anyway, i thought
03:43:46amiller:there's something useful in between "just me" and "everyone".... something like "sufficiently many [for some purpose]"
03:44:03petertodd:amiller: yeah, but stronger is to say whoever *needs* to care about it has to have it
03:44:04amiller:in the case of bitcoin transactions, i have this nice property that i just have to remember my key and my txout id
03:44:11amiller:that's not true
03:44:13kanzure:well, one of them was payee and payer
03:44:19amiller:i need to remember my key and txout i
03:44:33amiller:i'm the only one that "needs" to be able to spend my coin but i'm not the one who's storing the utxo data
03:44:47petertodd:amiller: compare it to anti-reply-shcemes where the majority of transaction data can be passed around privately
03:44:48amiller:i rely on all the miners storing all the utxo so ican find any of them and they'll validate my transaction
03:47:25petertodd:sure, but in Bitcoin those miners also have full transactions, which isn't necessarily needed for the system to work (e.g. anti-replay-only consensus)
03:48:07amiller:i'm not totally sure what you mean by anti-replay-only consensus but i'm pretty clear on Merkle Mountain Range so maybe you want to use that as your counterexample instead
03:48:27amiller:there, the person who wants to be able to spend the coin is repsonsible for keeping track of the state they need to prove a future tx of theirs is valid
03:48:40amiller:but still, there is *a* history of published information that everyone learns
03:48:57amiller:and that all the miners are expected to have seen and validated
03:50:08amiller:for example.... there's a possible bad outcome in MMR
03:50:19petertodd:lol, which one?
03:50:29amiller:where "51% of the miners" pass around a few blocks worth of updates
03:50:40petertodd:oh for sure, same deal with UTXO commitments
03:50:43amiller:but they don't actally publish it to the rest of the nodes
03:50:51amiller:the consensus still goes along okay because of that
03:51:06amiller:but now there are individuals who are *unable* to maintain their proof branches
03:51:11amiller:and thus unable to spend their coins
03:51:16petertodd:that problem was one of the things that lead me down this no validation path
03:51:18amiller:because they never received the data, and the miners who had it forgot it
03:51:25petertodd:yup, ugly problem!
03:51:44amiller:okay i'm about to give up again for tonight
03:51:45petertodd:proof of data posession seems to be 100% required for this stuff
03:51:50petertodd:same here
03:51:57amiller:this is an interesting area to go through but it seems to all be relegated to like
03:52:16amiller:"what happens when you relax the assumption/requirement that *everyone* gets to receive *all* the data in the blockchain"
03:52:43petertodd:I think that's 100% what it is - the question is simply one of how exactly does that relaxation occure
03:52:44amiller:is there still some useful notion of security then, on the requirement side can you achieve it (more cheaply), on the application side can you still use it for some functions
03:52:51amiller:ok good
03:53:59amiller:all the rest of the world of bitcoin proposals can be understood quite easily as following from the stronger assumption so i think i'm safe there, but it's good to point to this as a really useful thing to aim for next
03:54:44petertodd:yeah, although note how cross-chain-trades are your first entry into the idea that maybe it's not true that everyone has all the data
03:55:35amiller:yeah i have a useful notion of "all the *full* nodes" and also "mobile clients" that make queries and hold wallets and stuff
03:56:18petertodd:yes... and remember even in bitcoin there's not a clean distinction between full nodes and SPV - lots of shades of gray in between
03:57:06amiller:there's a clear notion of "full nodes" and everything else
03:57:19petertodd:I don't agree with that!
03:57:24amiller:actually for my purpose i am defining full node as seeing and validating every transaction
03:57:26Taek:In the non-validating chains, are miners proving that they have just the data in the block they mined, or are they proving they have all of the data in all the blocks they have mined?
03:57:32Taek:because the latter would seem to be necessary
03:57:47amiller:full (validating) node the "validating" there is implicit
03:58:09Taek:*all the blocks that have been mined
03:58:24petertodd:well, its' kinda late, but ask me again later about partial UTXO set nodes
03:58:49amiller:yeah i know all about those
03:58:55amiller:thanks for the discussion
04:01:48andytoshi:gmaxwell: :/ there are no explanations of dsa and schnorr on the web because until bitcoin they were totally obvious to anybody who had a need to care about them
04:02:19andytoshi:gmaxwell: plus the mechanics of ecdsa are totally irrelevant to bitcoin
04:03:40andytoshi:you could say "signatures are supposed to be "existentially unforgeable" which is exactly what it sounds like, ecdsa has not been shown to be this in any capacity whatsoever but NSA pressure + patent issues made it popular, so we all pretend that it's fine" end of story
04:20:53Emcy:so what youre saying is all the real deal stuff is patented up the ass on purpose to keep people away from it
04:21:28kanzure:and commerce control laws
05:01:20gmaxwell:amiller: you recursively prove.
05:01:53gmaxwell:"I know a valid state, that I made some change to" ... unfortunately this doesn't totally free you of knowing data. still has a need for a log size random lookup in the spendable coins.
05:03:09kanzure:i don't have a good sense for whether or not amiller's "an equation that balances out and none of the assumptions are the results themselves" target is achievable.
05:03:20kanzure:or the circumstances where that is definitely not achievable, for that matter.
05:03:51andytoshi:well, "definitely not achievable" would only be in case of an impossibility proof..
05:06:53kanzure:but just an impossibility proof of that particular type of modeling
05:46:15lechuga_:i wonder why no1 has built a true universal p2p protocol
05:47:14lechuga_:fully nat traversing w/encryption + namecoin style dyndyns.org-ish name resolution
05:49:13lechuga_:onion routed
06:22:03myeaglef1ies:myeaglef1ies is now known as myeagleflies
06:25:55Luke-Jr:lechuga_: sounds like tor?
06:26:02Luke-Jr:or you mean without the directories?
08:05:15wolfe.freenode.net:topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
08:05:15wolfe.freenode.net:Users on #bitcoin-wizards: andy-logbot torsthaldo RoboTedd_ HaltingState mkarrer aburan28 tromp_ go1111111 wfbarks kgk_ nsh todays_tomorrow TheSeven koshii c0rw1n_ eslbaer_ Sangheili lianj nuke1989 myeagleflies SomeoneWeird justanotheruser Fistful_of_coins Krellan shesek CryptOprah Dr-G3 DoctorBTC artilectinc altoz rdponticelli moa Max_H3adr00m devrandom samson_ Emcy Meeh nanotube jgarzik d4de^^ gavinandresen mortale emsid Iriez [Derek] comboy burcin gsdgdfs
08:05:15wolfe.freenode.net:Users on #bitcoin-wizards: NikolaiToryzin Anduck HM arowser warren Guest45377 Logicwax coryfields_ [\\\] pigeons xenogis Luke-Jr sipa gmaxwell Taek kanzure SDCDev iddo_ _2539 LaptopZZ_ lnovyz Grishnakh dgenr8 Adlai hguux Starduster zwischenzug spinza derzp Alanius rfreeman_w K1773R grandmaster2 phantomcircuit wizkid057 kumavis heath Graftec wiretapped a5m0 andytoshi bobke petertodd BigBitz waxwing pi07r fanquake wumpus espes__ BrainOverfl0w ebfull kaene digitalmagus
08:05:15wolfe.freenode.net:Users on #bitcoin-wizards: CodeShark epscy smooth BlueMatt Graet LarsLarsen @gwillen sl01 copumpkin dansmith_btc artifexd michagogo tromp bbrittain weex gribble EasyAt Kretchfoop jaekwon Muis Hunger-- jrayhawk_ firepacket berndj @ChanServ phedny lechuga_ abc56889 throughnothing harrow asoltys forrestv fluffypony mr_burdell Apocalyptic kinlo midnightmagic starsoccer so ahmed_ Gnosis Keefe pajarillo roasbeef mmozeiko ryan-c otoburb helo [Tristan] TD-Linux catcow danneu
08:05:15wolfe.freenode.net:Users on #bitcoin-wizards: UukGoblin poggy coryfields kgk btc_ crescendo amiller Eliel optimator zibbo_ jbenet mappum MRL-Relay Dyaheon livegnik hollandais yoleaux [d__d]
08:35:44davidlatapie:davidlatapie has left #bitcoin-wizards
09:15:13davidlatapie:davidlatapie has left #bitcoin-wizards
09:26:15gmaxwell:andytoshi: I still don't get why people keep posting microscopic scale overviews that realy convey no understanding at all.
09:26:42gmaxwell:it's not just that one. there are a several others with almost identical content.
09:27:32gmaxwell:similar completely opaque dots over a graph diagram. Passable chord and tangent explination that more or less makes sense (but then a weak explination of how the geometric addition process is the same as the numeric one or why it works over a finite field)
09:27:55gmaxwell:but then no real sense of the cryptography... I think if that had been my introduction to crypto I wouldn't have gotten anywhere.
09:33:41gwillen:gmaxwell: I dunno, the version with the reals was enough for me to at least understand the general notion of an elliptic curve
09:33:54gwillen:I say, as someone who doesn't really understand why it works over a finite field
09:34:14gwillen:(and by the reals I mean the real projective plane, IIRC)
09:35:16gmaxwell:gwillen: yea, thats nice .. and learning chord and tangent rule for addition is nice.. but they kinda stop there. Which is not super helpful... mostly I was complaining that not a single one explains ecdsa or schnorr, which can be understood without understanding elliptic curves at all.
09:35:26gwillen:ahhh, *nods*
09:36:17gmaxwell:virtually all the crypto requires no understanding of how the underlying group works either... you might want to know something about it to implement it (or not, a basic understanding doesn't get you an acceptably fast implementation)
09:36:23gwillen:* gwillen nods
09:36:38gwillen:in fact, a basic understanding probably gets you a broken implementation
09:36:52gwillen:at the least it gets you one with severe timing attack issues
09:36:54gmaxwell:yea, actually for the kinds of curves we use they absolutely will.
09:37:44gmaxwell:Not just that, the addition rule is irregular, adding a point to itself (or to its sign-flipped mirror) requires a different addition formula.
09:37:55gwillen:so if you miss the special case you lose
09:37:59gwillen:and if you don't miss it, you lose on timing
09:38:22gmaxwell:the doubling you can't miss, but the other special cases you can. And timing too... oh well, in that case you'd be just as bad as openssl :(
09:38:44gwillen:not quite as bad, given the current ssl CVE
09:39:27gmaxwell:Understanding how the signature works, (while blackboxing the hardness of discrete log in whatever you're using; since understanding anything about that is its own epic journey in number theory)
09:39:57gmaxwell:is pretty useful though... even knowing nothing about implementing the group.
09:40:01gwillen:"understanding the hardness of discrete log" seems like an open problem, since proving the hardness of discrete log is an open problem ;-)
09:40:11gwillen:* gwillen nods
09:40:28hearn:by the time everyone is fully up to speed with ecc and related algorithms, it'll be time to switch to lwe :)
09:40:59gmaxwell:gwillen: right. But there is still lots to understand, e.g. there are huge classes of curves which superficially look like the ones we use for crypto, but for which discrete log is basically trivial.
09:41:08gwillen:* gwillen nods
09:41:43gwillen:luckily there are smart people who have picked out good curves, so if I ever have to pick out a curve, I do what they tell me ;-)
09:41:49gwillen:I hear djb has an entire website about this.
09:42:13gmaxwell:He does, I'm a little unhappy with it. Surprise: the only good curves are his.
09:42:35gwillen:well, if you've ever been acquainted with the djb koolaid before, you kind of know how the story goes
09:42:58gwillen:his koolaid is generally quite good as long as you can tolerate it... ;-)
09:43:26gwillen:but it doesn't shock me that his criteria happen to be the ones that pick out his curves
09:43:36gwillen:since he probably already had them in mind, unpublished, when picking those curves in the first place
09:43:36gmaxwell:It makes a lot of good points and has nice analysis. but does some stuff I think are basically pure sales. E.g. has some criteria that very few applications care about at all... or knocks curves on features for performance, while ignoring the fact that his own has a completely isomorphic structure.
09:43:53gmaxwell:gwillen: other way around.
09:44:06gwillen:well, I'm trying to give him the benefit of the doubt here :-P
09:44:33gwillen:I think he's more reasonable than to literally pick his criteria based on his own curves
09:45:01gwillen:I can totally believe he would call the ones his own curves fulfill more important than the ones they don't
09:45:27gwillen:anyway, I'm sympathetic to both sides on 'criteria that mostly nobody cares about, except when you do'
09:46:19gwillen:I didn't follow the second half of that sentence, except as to where he's dinging people for doing things his own curves also do under some isomorphism
09:46:38gmaxwell:gwillen: E.g. he dings secp256k1 because it has an efficient endomorphism (low CM, since thats the requirement to actually find it), on the basis that the endomorphism reduces discrete log security by 1.5 bits (for exactly the same reason that it speeds up verification), but then his curve is constructed over an extension field specifically to give it an equivilently functional operation, which also knocks off 1.5 bits. No ding. And ...
09:46:44gmaxwell:... moreover the choice of the extension field gives it a cofactor of 8, which lowers the curve order and effectively knocks of 3 bits. Now a few bits here and there, who cares.. but not a very even converage. Esp when this analysis all ends up in a yes/no table.
09:47:00gwillen:* gwillen nods
09:47:11gmaxwell:and well meaning concerned people posting on bitcointalk "omg secp256k1 is unsafe"
09:47:13gwillen:that's kind of unfortunate since I don't have the background to spot it
09:47:19gwillen:(I mean, from my perspective)
09:47:32gwillen:good to know I guess
09:49:55davidlatapie_:davidlatapie_ has left #bitcoin-wizards
09:50:01gmaxwell:It's kinda odd though his cureves come from a new family that are recently trendy... the whole notion is that if you construct them over some extension field (prime ^ 2) you can get the endomorphism speedup trick easily (basically the trick means you can multiply a point by some number for nearly free, and this lets you decompose a multiply into two half sized parts) ... vs in the regular prime field case there are very few ...
09:50:07gmaxwell:... parameters that yield a usable curve with that speedup trick available.
09:51:15gmaxwell:(that requirement plus that it be a group of prime order and the selection of the underlying field uniquely selects secp256k1 alone)
09:52:20gmaxwell:I think there is kind of a disjointness with most of the interest in DJB curves... If you ask people what they use them for: The answer you get is security. If you ask DJB what the design criteria was, he should answer performance.
09:53:46gwillen:* gwillen nods
09:53:57gwillen:"performant security" :-)
09:54:32gmaxwell:It's a good criteria in general.
09:59:29gmaxwell:though if you were optimizing over security, .. you might use more well known constructions. The extension field approach may open new potential attack avenues. (right now it's believed not, ... but over extension p^x where x is composite is pretty much totally busted for most parameters; I trust DJB to make the best available decisions there but its not a security conservative one (though on that basis, neither is Bitcoin's I suppose))
10:01:25gwillen:* gwillen nods
10:01:58gmaxwell:in any case, I've already whined at djb some and he changed the page some, which is good.
10:02:20gwillen:haha, I'm both amazed and pleased that he listened
10:02:44gmaxwell:He sounded like he was blowing me off completely, I was surprised that he changed the pages.
10:03:00gwillen:what'd he change?
10:05:06gmaxwell:His initial definition of rigidity was too narrow, I emailed told him it was attackable, he responded disagreeing. I sent him a sage notebook demonstrating the attack (hypothetical 'rigid' curve paremters, plus a cryptosystem that was weak based on them). He responded basically saying my example was contrived (indeed, it was, but I'd said as much but pointed out that such things have been used before). About a week later he changed ...
10:05:12gmaxwell:... the page to revise the definition and note the concern... and also added information about his own curves to show them rigid under the new narrower sense.
10:05:31gwillen:* gwillen nods
10:05:38gmaxwell:(rigid = means you had limited freedom in picking the parametrs to hide backdoors)
10:06:06gmaxwell:(I showed that selection of the generator lets you know the discrete log of a point which otherwise looks 'nothing up my sleeve')
10:07:24gmaxwell:so for example in the context of bitcoin, if someone from secg shows up claiming coins sent to pubkey 0xdeadbeef are really unspendable because no one knows the private key for that, you may not want to believe them.
10:08:11gwillen:(is this a case of, you get _one_ free gimmicked point per curve? Or a whole lot of them? By cheating in this way?)
10:08:19gmaxwell:just one.
10:08:29gwillen:* gwillen nods
10:09:35gmaxwell:gwillen: standards group that published secp256k1
10:09:42gwillen:ahh, *nods*
12:05:49hearn__:hearn__ is now known as hearn
12:27:14andytoshi:gmaxwell: hmm, i guess i have seen basically that article many times ... i think it was even in AA's book
12:27:53andytoshi:if i had to guess, i'd say that the authors "see" why discrete log is hard once they have a visualization of what the addition operator actually looks like?
12:28:04andytoshi:and want to share that "insight"
13:01:58Aquent:Aquent is now known as winteriscoming
14:28:28c0rw1n_:c0rw1n_ is now known as c0rw1n
15:13:07winteriscoming:winteriscoming is now known as mooniscoming
15:20:43mooniscoming:mooniscoming is now known as Aquent
17:19:40gmaxwell:So neat thought, I've linked a number of times to http://www.cs.tau.ac.il/~benriva/ccs11.pdf which is the scheme for verifyable computation with N servers, using just hashing, where servers give a hash of their transcript of computation, and if they differe you do log() queries to find their point of disagreement so you know which server is lying.
17:21:26gmaxwell:One extra application of this would be taking otherwise not cheaply verifyable information (like a UTXO hash) that nodes aren't putting in the blockchain... and then offering it up. You know, the unauthenticated queries we've lamented.
17:22:10gmaxwell:So a client connects to all the servers they can reach, and then if there are hash disagreements they challenge the servers to find out which ones are right.
17:22:54gmaxwell:the data is not cheaply authenticable when you have a single server, but when two disagree you can tell: "X says utxo 1 exists and you say it doesn't" "no, it was spent 'here'"
17:23:20gmaxwell:and so this way you can get "you need speak to only one honest peer" without a commitment in the blockchain.
17:31:33gmaxwell:You were already pretty hosed if you could find no honest servers at all. So this is not so bad. (not like commited data already doesn't have its limits... someone can just mine some blocks to fake it)
17:31:44amiller:gmaxwell, have you seen versum
17:33:54gmaxwell:amiller: just got sent a link to it from someone else in fact. Cool. Don't know why this wasn't the first application I thought of when seeing ccs11.pdf
18:11:48amiller:i think versum is great, i wish i had thought of it
18:12:21amiller:they presented it in a pretty general way which is cool but their implementation is just a go program for a specific application (well, it's specifically exactly the application you're interested, UTXO checking and like account balances)
18:12:40amiller:but i want to make a version of versum for my lambda-auth generic merkle tree language
18:13:54gmaxwell:I am very much not interested in "account balances" myself.
18:21:55gmaxwell:But there has been talk about hurrying up and getting some more commited data in, so this could be a reasonable half step.
18:23:29jgarzik:gmaxwell, interesting
18:23:36jgarzik:RE moxiebox
18:25:28gmaxwell:yea, it would work fine for moxiebox... though most of our applications need non-interactive verification. E.g. couldn't use it for script.
18:28:04gmaxwell:we should perhaps think of a simple beacon protocol e.g. udp even, where you can ask a node for its recent header(hashes) and other commitments.. so you could reasonably have hosts probe a singnificant fraction of the network in a scalable way.
18:32:13jgarzik:I thought about this a bit in the past, where data is sometimes more expensive to fully authenticate. Seemed an iterative/progressive method could be used to probe disagreements between servers/oracles, when working with larger data sets. Or put more simply and obviously: Validate the first GB, then the first 5GB, and so on. Not a full solution, but like the blockchain, makes proofs progressively more expensive while quickly searching
18:32:13jgarzik:for the most likely case, a quickly discover-able disagreement.
18:33:48gmaxwell:right with a hashtree over operations you need log(transcript) rounds to find disagreements.. and then once you find the first point of disagreement you figure out who is wrong.
18:34:02gmaxwell:(obviously this requires completely determinstic computation)
18:43:00woah:would it ever be feasible to mine human readable public key hashes?
18:58:04lnovyz:lnovyz is now known as lnovy
22:07:56SDCDev:SDCDev is now known as somerandomguy332
22:08:18somerandomguy332:somerandomguy332 is now known as SDCDev