| 00:12:53 | gmaxwell: | 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:11 | tacotime: | Did anyone review AnonCoin's improvement to Sander's RSA UFO paper? |
| 00:21:15 | tacotime: | https://wiki.anoncoin.net/RSA_UFO |
| 00:21:47 | gmaxwell: | I think I saw that before and it made no sense. Is that the thing where it's "multiple small UFO" ? |
| 00:22:01 | tacotime: | Yeah it looks like it |
| 00:22:09 | gmaxwell: | I was excited when I heard the ideas and the numbers I came up with were not improvements. |
| 00:22:50 | gmaxwell: | 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:27 | gmaxwell: | 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:14 | gmaxwell: | loading that page, the security argument they give there is somewhat bogus. |
| 00:25:24 | gmaxwell: | it's like the NIST argument that the NIST curves are 'random'. |
| 00:26:10 | gmaxwell: | 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:30 | tacotime: | 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:27 | tacotime: | Proofs are also stored off chain |
| 00:27:34 | tacotime: | Which is a whole separate issue in and of itself |
| 00:27:52 | gmaxwell: | 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:05 | gmaxwell: | it should be several times slower than libzerocoin. |
| 00:28:30 | tacotime: | They're saying they did, I guess we'll find out when they publish their code tomorrow. |
| 01:33:17 | CryptOprah_: | CryptOprah_ is now known as CryptOprah |
| 01:43:04 | SomeoneWeird_: | SomeoneWeird_ is now known as SomeoneWeird |
| 01:43:34 | SomeoneWeird: | SomeoneWeird is now known as Guest83486 |
| 01:48:06 | amiller: | i think i finally have a good way of organizing all the interesting bitcoin proposals/ideas for my systematization of knowledge paper |
| 01:48:09 | Guest83486: | Guest83486 is now known as SomeoneWeird |
| 01:49:26 | amiller: | 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:53 | amiller: | 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:35 | amiller: | 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:53 | amiller: | 2. validation rules and algorithms for checking/proving that rules are followed |
| 01:51:29 | amiller: | rules include the bitcoin scripts, proposed new opcodes, things like zerocoin/zerocash which involve basically new transaction types |
| 01:52:12 | execut3: | execut3 is now known as shesek |
| 01:52:33 | amiller: | 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:52 | amiller: | as for ways of enforcing validation rules, |
| 01:53:41 | amiller: | 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:58 | amiller: | and a hypothetical SnarkCoin where verification of everything is O(1) |
| 01:55:01 | amiller: | 3. protocols built using bitcoin (or something closely related) as a component |
| 01:55:59 | amiller: | the main way to break things down here are the models and trust assumptions involved |
| 01:56:39 | amiller: | a) two or multiparty protocols with minimal trust, like the microcontracts gradual release protocol, the lottery game |
| 01:57:06 | amiller: | 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:24 | amiller: | c) "trust-but-verify" sort of auditable protocols like green addresses |
| 01:57:27 | kanzure: | 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:39 | amiller: | where a third party can temporarily break something but the blockchain can be used to provide evidence |
| 01:57:48 | amiller: | also all the "fraud proof" sort of ideas go in here |
| 01:58:18 | amiller: | i think colored coins and mastercoin in their typical use case go here |
| 01:58:42 | amiller: | 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:12 | amiller: | 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:31 | amiller: | 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:17 | kanzure: | maybe there can be a "cost of trust" measurement. hm. |
| 02:22:52 | petertodd: | 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:40 | amiller: | 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:55 | petertodd: | 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:56 | petertodd: | 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:02 | nuke_: | nuke_ is now known as nuke1989 |
| 02:26:53 | petertodd: | amiller: all fairly weak use-cases, but worth mentioning for completeness |
| 02:27:11 | amiller: | i think completeness isn't really a goal |
| 02:27:36 | petertodd: | amiller: well, how you define 'systematization' is up to you :) |
| 02:28:06 | amiller: | 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:42 | amiller: | b) to include the most interesting or important (admittedly subjective) ideas and fit them in |
| 02:29:18 | petertodd: | amiller: well, in that case leave it out |
| 02:29:55 | amiller: | it's a cool idea though now i'm still thinking about it |
| 02:30:40 | amiller: | you could have ehteruem without the data store |
| 02:32:25 | petertodd: | 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:31 | petertodd: | ... protocols they aren't necessarily even needed |
| 02:33:05 | amiller: | yeah i think that makes sense |
| 02:34:07 | amiller: | 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:22 | amiller: | so it's pretty cool to add in "blockchain" as another kind of component to add to these |
| 02:34:57 | petertodd: | 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:35:18 | amiller: | yeah |
| 02:36:29 | petertodd: | where would hub-and-spoke micropayments fit in this systematization? |
| 02:37:13 | amiller: | in 3.something somewhere... i'm a little hazier on how many "different" models there are |
| 02:37:54 | amiller: | it's sort of halfway between semi-trusted (for availability if not everything else) and the gradual release two party gcase |
| 02:38:00 | kanzure: | forcing categories might be wrong anyway |
| 02:38:43 | amiller: | 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:44 | petertodd: | amiller: yeah, it's not a fundemental type of model |
| 02:39:22 | amiller: | 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:10 | amiller: | 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:51 | amiller: | 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:33 | petertodd: | 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:54 | petertodd: | (or equally, generalize!) |
| 02:42:57 | moa: | 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:03 | amiller: | i don't know where to put merged mining |
| 02:43:10 | amiller: | that's one of the edge cases i really don't know where to put |
| 02:43:20 | kanzure: | why are you bothering with categories anyway? |
| 02:43:21 | petertodd: | amiller: yeah, merge-mining is really odd... asymetric is the word that comes to mind |
| 02:43:32 | amiller: | i don't think it's asymmetric you could have mutually merge mined currencies |
| 02:43:53 | petertodd: | amiller: even in that case for a given attacker the costs are asymmetric |
| 02:44:15 | petertodd: | amiller: maybe a better word is non-uniform |
| 02:44:26 | amiller: | 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:27 | kanzure: | instead of categories you can just call it a work of observational cryptography |
| 02:44:56 | amiller: | kanzure, that seems fuzzy and unprincipled, i don't know how i can be rigorous without some approach like this |
| 02:45:22 | amiller: | 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:33 | kanzure: | where rigor is "adequately predicting future models that improve on current implementations" ? |
| 02:45:45 | petertodd: | 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:04 | petertodd: | amiller: (remember that all this PoW stuff does is resist sybil attacks!) |
| 02:46:06 | amiller: | 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:12 | moa: | the miller 'trust' number sounds good .... |
| 02:46:25 | amiller: | i don't think trust as a 'number' function makes much sense |
| 02:46:27 | moa: | jk |
| 02:46:43 | amiller: | that's a response more to kanzure's earlier statements than moa's line :p |
| 02:46:52 | moa: | non-dimensionalised trust |
| 02:46:59 | kanzure: | well it has to be something, even though not a number |
| 02:47:06 | kanzure: | (otherwise it's not worth discussing) |
| 02:47:33 | amiller: | 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:44 | petertodd: | 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:01 | moa: | qualitatively it appears there is a 'spectrum' of trust |
| 02:48:10 | petertodd: | moa: thus systems with a high k-trust are the weakest and most reliant on it |
| 02:48:19 | moa: | hmmm |
| 02:48:30 | amiller: | 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:35 | kanzure: | amiller: what about, "readers walk away with dramatically improved tools to work in this space"? |
| 02:48:59 | amiller: | 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:40 | petertodd: | amiller: don't forget to include a column labeled "sum total of bribes received from schemes pumpers" |
| 02:50:50 | kanzure: | amiller: what about a sort of rigor focused on listing known attacks on slightly weaker implementations/proposals |
| 02:50:51 | amiller: | ha. |
| 02:51:10 | kanzure: | (or even those current implementations) |
| 02:51:11 | petertodd: | amiller: send me your address and I'll send you $5 for treechains |
| 02:51:20 | amiller: | petertodd, one thing i'm doing is trying to avoid discussing 'altcoins' as opposed to the sort of abstracted concepts/ideas |
| 02:51:29 | amiller: | any given altcoin generally implements a dozen kinds of changes |
| 02:51:37 | moa: | 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:59 | amiller: | 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:04 | petertodd: | 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:16 | petertodd: | amiller: oh, that's brilliant! |
| 02:52:28 | amiller: | sergio lerner gave me a big pull request full of explanations of every single one of his altcoins |
| 02:52:42 | petertodd: | good riddance.. |
| 02:52:42 | NewLiberty: | hatred and fear are cousins. The only thing that can really kill bitcoin is a better bitcoin |
| 02:52:55 | amiller: | 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:05 | kanzure: | petertodd: that hatred is probably just because nobody has time to sit around debunking everything and proposing attacks. |
| 02:53:25 | amiller: | that style is ok i guess but it makes it way hard to separate out the meaningful parts |
| 02:53:27 | petertodd: | 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:48 | petertodd: | amiller: have any had any success? |
| 02:53:49 | amiller: | petertodd, you're required by professional ethics to turn in all your coins to jeff to hold in escrow |
| 02:54:07 | petertodd: | amiller: sorry, I blew it all on hookers and blow in vegas last week |
| 02:54:40 | petertodd: | amiller: (actually crack due to the low price...) |
| 02:54:48 | moa: | poker face |
| 02:55:03 | amiller: | 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:26 | NewLiberty: | petertodd, good point. a worse bitcoin could also kill it, if folks follow an unfortunate fork |
| 02:55:34 | amiller: | 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:49 | amiller: | side chains can have two pow chains that validate SPV proofs about each other |
| 02:55:59 | petertodd: | 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:18 | amiller: | petertodd, okay so that's a good question to analyze |
| 02:56:26 | amiller: | what's the basis for a complete scalable system |
| 02:56:32 | moa: | cross-chain multi-sig payment channels? |
| 02:56:33 | petertodd: | amiller: so ok, you have a measure of how the security of a given scheme degrades as it scales |
| 02:56:35 | amiller: | and does it still follow the basic structure of pow-consensus blockchain |
| 02:57:33 | petertodd: | 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:51 | petertodd: | amiller: sidechains is like that too, but MM-sidechains potentially even worse because attacks are free |
| 02:57:55 | NewLiberty: | so merge mining |
| 02:58:24 | NewLiberty: | <-- types to slowly in my old age |
| 02:58:42 | amiller: | NewLiberty, that's fine you're just on the 0.25 -wizards tree chain |
| 02:58:52 | petertodd: | lololol |
| 02:59:03 | amiller: | the attacks-free part of MM is because of merge mining and not unique to the side chain part at all |
| 02:59:33 | amiller: | just a bunch of alt coins scaling up whatever is just as applicable to a bunch of altcoins |
| 02:59:34 | jtimon: | plus is false, there's an opportunity cost |
| 02:59:45 | amiller: | i dont see how this involves the "side chains" part of side chains at all |
| 03:00:09 | jtimon: | and only miners can do it, otherwise petertodd would have proven his point by attacking namecoin for free long ago |
| 03:00:12 | petertodd: | 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:41 | petertodd: | amiller: which gets back to my earlier point re: how secure are systems against sybil attacks |
| 03:00:52 | petertodd: | amiller: and that in turn applies to fraud proof schemes too! |
| 03:01:06 | amiller: | there's in general a ciruclarity i have to cut somewhere |
| 03:01:20 | amiller: | i have plenty of text (from coauthors) about consensus properties and the incentives that lead to them |
| 03:01:42 | amiller: | 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:45 | petertodd: | amiller: is this circularity, or a n-dimensional solution space? |
| 03:01:54 | amiller: | * amiller mind explodes |
| 03:02:13 | amiller: | i have a wedge which involves to one side, the consensus properties are a goal, |
| 03:02:19 | amiller: | and to the other side, the consensus properties are an assumption |
| 03:02:21 | petertodd: | 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:34 | amiller: | 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:50 | petertodd: | remember my thought experience of "broadcast coin" where you simply broadcast your transactions and rely on you not being sybil attacked |
| 03:02:51 | amiller: | can cause the incentives to break down that are used to justify the assumptions upon which we build the applications anyway |
| 03:03:18 | amiller: | i don't have "sybil attack resistance" as a first class concept in my current schema |
| 03:03:28 | petertodd: | I think you absolutely have to |
| 03:03:32 | amiller: | try talking me into it and i'll see if i feel like it. |
| 03:03:41 | kanzure: | sybil attack resistance is just "treat everyone as an adversary" or "don't assume that identity is extremely expensive or meaningful" |
| 03:03:45 | amiller: | i have something i think you'd recognize as proof of publication |
| 03:04:03 | petertodd: | so, do you agree that if sybil attacks weren't an issue, you'd just broadcast transactions? |
| 03:04:08 | petertodd: | amiller: ? |
| 03:04:15 | amiller: | 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:22 | kanzure: | what sort of sybil are we talking about here.. p2p nodes? |
| 03:04:44 | amiller: | to even call it sybil i need to assume something like 1 transcation per 1 node or something |
| 03:04:44 | petertodd: | kanzure: could come in multiple forms! |
| 03:05:05 | amiller: | 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:25 | petertodd: | 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:14 | amiller: | 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:57 | petertodd: | 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:39 | amiller: | well.... okay this is an interesting point but i think my current schema is okay.... |
| 03:08:42 | petertodd: | 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:06 | amiller: | 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:14 | amiller: | so N transactions or whatever |
| 03:09:27 | petertodd: | 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:54 | petertodd: | hmm, I'm not sure I'd talk about it in terms of 'n transactions', but maybe that makes sense |
| 03:10:16 | petertodd: | so Ripple consensus is local, the cost to join is zero... but membership is defined by who trusts you |
| 03:11:16 | petertodd: | 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:11:47 | amiller: | hrm |
| 03:12:06 | petertodd: | (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:16 | amiller: | okay good this is the stuff from you that i wanted to see if my schema could withstand. |
| 03:12:22 | amiller: | so in my extreme simplifeid rule set |
| 03:12:29 | amiller: | i'm still assuming that consensus means "publishing" |
| 03:12:41 | amiller: | yet there are no direct incentives to actually look at the data |
| 03:12:45 | petertodd: | yeah, publishing something - zero-knowledge consensus isn't a thing AFAIK |
| 03:12:51 | amiller: | you can save cost by not fetching it and your peers can save cost by not sending it |
| 03:13:06 | petertodd: | right, OTOH your peers have (weak) incentives to catch you doing that in many schemes |
| 03:13:08 | amiller: | my usual answer is the storage puzzle helps a bit but i'm not confident about that |
| 03:13:32 | amiller: | 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:59 | petertodd: | 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:29 | amiller: | i guess, i don't see how you actually get around that sort of reasoning |
| 03:14:30 | petertodd: | (and actually, s/treechains/generic data-publishing-only chains/) |
| 03:14:44 | petertodd: | amiller: ? |
| 03:15:20 | amiller: | 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:33 | amiller: | 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:46 | petertodd: | you mean with respect to this notion of enforcing publication? |
| 03:15:49 | amiller: | 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:52 | amiller: | yes |
| 03:15:57 | petertodd: | so remember my 'disentangling mining' paper |
| 03:15:58 | amiller: | so there's a notion of "the history" and "all the nodes" |
| 03:15:59 | petertodd: | ? |
| 03:16:13 | amiller: | yes i "remember" it but not understand it |
| 03:16:30 | petertodd: | 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:31 | kanzure: | sometimes nodes get kicked out of the consesus set, so there are different histories (especially in hard fork scenarios) |
| 03:16:54 | amiller: | okay |
| 03:17:07 | petertodd: | 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:12 | amiller: | 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:50 | petertodd: | 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:32 | amiller: | i'm lost about what that means |
| 03:18:48 | amiller: | 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:06 | kanzure: | no, use petertodd's consensus domain idea instead |
| 03:19:19 | amiller: | s/consensus set/consensus domain/ |
| 03:19:19 | petertodd: | 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:20 | gmaxwell: | petertodd: So the cost of attacking bitcoin is free? |
| 03:19:36 | kanzure: | gmaxwell: unsuccessfully? probably? |
| 03:19:51 | petertodd: | 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:05 | gmaxwell: | (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:09 | kanzure: | anyone can delete their blockchain on their computer, is that an attack.. |
| 03:20:23 | kanzure: | although you may be talking about attacking the bitcoin network instead. oops. |
| 03:20:28 | petertodd: | 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:38 | amiller: | 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:42 | petertodd: | gmaxwell: ? |
| 03:21:15 | petertodd: | amiller: think of publishing as the first step in the process by which you establish consensus about what history is |
| 03:22:29 | petertodd: | 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:44 | gmaxwell: | 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:00 | amiller: | petertodd, you need to go back and help me constrain what you mean by "consensus domains" |
| 03:23:16 | gmaxwell: | So that argument needs to be narrowed some or it's-- in effect-- saying attacking Bitcoin is free because namecoin exists. :) |
| 03:24:10 | petertodd: | 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:20 | kanzure: | 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:50 | petertodd: | 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:50 | amiller: | 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:19 | gmaxwell: | petertodd: I'm not making an argument, just pointing out that what you were saying was insufficiently tight. |
| 03:25:20 | petertodd: | 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:54 | amiller: | 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:00 | petertodd: | 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:26 | petertodd: | 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:37 | amiller: | petertodd, that seems application specific and i was really hoping for a nice way of chopping the circularity somewhere convenient |
| 03:26:45 | amiller: | petertodd, yes i see that part |
| 03:26:46 | gmaxwell: | 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:52 | kanzure: | amiller: wlel, it's certainly not determined prior to connection (except for high-level forks running on other ports anyway) |
| 03:26:59 | petertodd: | gmaxwell: that's an apology :) |
| 03:27:03 | gmaxwell: | oh |
| 03:27:06 | gmaxwell: | :) |
| 03:27:23 | petertodd: | 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:36 | amiller: | i hereby apologize in advance, for everything |
| 03:27:42 | amiller: | cheers |
| 03:27:52 | petertodd: | amiller: fuck you and die in a fire, your mother was an elderberry |
| 03:28:02 | kanzure: | me next |
| 03:28:14 | amiller: | petertodd, no i don't agree with that |
| 03:28:20 | petertodd: | kanzure: fuck you, your name sounds like a particularly bad operating system |
| 03:28:37 | petertodd: | amiller: well, in the sense that the blocks you produced would be "valid" blocks |
| 03:28:45 | amiller: | you can generally "safely" mine already without validating anything |
| 03:28:51 | amiller: | that's not necessarily true either |
| 03:28:55 | petertodd: | amiller: yeah... and that's a flaw :) |
| 03:28:55 | amiller: | evne wihtout knowing the contents... |
| 03:29:02 | amiller: | you could potentially need to reveal the contents |
| 03:29:15 | amiller: | i can make a false commitment to some untyped data that i still am unable to reveal |
| 03:29:24 | kanzure: | you don't need to validate transactions but you are mining based on history still, aren't you |
| 03:29:27 | kanzure: | does that count as validating |
| 03:30:17 | petertodd: | 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:02 | amiller: | 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:02 | moa: | 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:06 | petertodd: | 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:27 | petertodd: | amiller: go |
| 03:31:28 | amiller: | i think we're about to talk about a blockchain with no validation rules, just untyepd unregulated data packets in the transactions |
| 03:31:35 | petertodd: | amiller: right |
| 03:31:36 | amiller: | i'd call that a "no transaction rules" blockchain |
| 03:31:45 | amiller: | yeah and that implies no index |
| 03:31:52 | amiller: | okay what do you mean by prove and coin history thouhg |
| 03:32:28 | petertodd: | 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:36 | gmaxwell: | petertodd: I think there is a middle ground where the blockchain is only a anti-replay oracle but has no other rules. |
| 03:32:46 | gmaxwell: | (er there is a middle ground which is _very_ interesting) |
| 03:33:11 | gmaxwell: | Because it lets you work with completely hash-compressed and encrypted data. |
| 03:33:49 | petertodd: | gmaxwell: right, and actually that's a more interesting middleground than my example above re: script-verification-only chains |
| 03:34:20 | petertodd: | gmaxwell: (granted, anti-replay needs authentication... so maybe that does encompase it?) |
| 03:34:44 | amiller: | 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:02 | gmaxwell: | 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:24 | petertodd: | amiller: yeah, and once you accept that works, you "just" need to optimize it until it's practical :) |
| 03:36:27 | petertodd: | 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:34 | gmaxwell: | RT MM secutiy I'd suggest something like "the cost of attacking is the oppturnity value of |
| 03:37:37 | gmaxwell: | not attacking, blockchains with low income for miners are not secure." ... |
| 03:37:41 | gmaxwell: | I think this is actually the key point, not sure if MM actually really |
| 03:37:43 | gmaxwell: | matters other than it can make the hashrate deceptive. |
| 03:37:46 | gmaxwell: | E.g. In the worst case namecoin arguably only has 50+episilon NMC/block security, even though |
| 03:37:49 | gmaxwell: | the difficulty is 90% of bitcoin's. There is probably some miner altriusm |
| 03:37:52 | gmaxwell: | term that ought to be included there. |
| 03:38:00 | gmaxwell: | er WRT instead of RT there. |
| 03:38:05 | petertodd: | gmaxwell: makes sense |
| 03:38:07 | amiller: | 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:36 | amiller: | you're trying to talk me into dropping "everyone sees all the data" as a basic common goal/assumption in blockchain sstems |
| 03:39:19 | petertodd: | 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:34 | petertodd: | amiller: heh, of course I am, "everyone sees all the data" is obviously unscalable |
| 03:39:48 | gmaxwell: | 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:37 | petertodd: | 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:56 | amiller: | 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:31 | amiller: | 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:13 | petertodd: | 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:14 | amiller: | maybe what you're going to say next is, whoever cares about it has to have it |
| 03:42:15 | kanzure: | non-miners aren't building on top of history anyway, i thought |
| 03:43:46 | amiller: | there's something useful in between "just me" and "everyone".... something like "sufficiently many [for some purpose]" |
| 03:44:03 | petertodd: | amiller: yeah, but stronger is to say whoever *needs* to care about it has to have it |
| 03:44:04 | amiller: | 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:11 | amiller: | that's not true |
| 03:44:13 | kanzure: | well, one of them was payee and payer |
| 03:44:19 | amiller: | i need to remember my key and txout i |
| 03:44:33 | amiller: | 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:47 | petertodd: | amiller: compare it to anti-reply-shcemes where the majority of transaction data can be passed around privately |
| 03:44:48 | amiller: | i rely on all the miners storing all the utxo so ican find any of them and they'll validate my transaction |
| 03:47:25 | petertodd: | 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:07 | amiller: | 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:27 | amiller: | 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:40 | amiller: | but still, there is *a* history of published information that everyone learns |
| 03:48:57 | amiller: | and that all the miners are expected to have seen and validated |
| 03:50:08 | amiller: | for example.... there's a possible bad outcome in MMR |
| 03:50:19 | petertodd: | lol, which one? |
| 03:50:29 | amiller: | where "51% of the miners" pass around a few blocks worth of updates |
| 03:50:40 | petertodd: | oh for sure, same deal with UTXO commitments |
| 03:50:43 | amiller: | but they don't actally publish it to the rest of the nodes |
| 03:50:51 | amiller: | the consensus still goes along okay because of that |
| 03:51:06 | amiller: | but now there are individuals who are *unable* to maintain their proof branches |
| 03:51:11 | amiller: | and thus unable to spend their coins |
| 03:51:16 | petertodd: | that problem was one of the things that lead me down this no validation path |
| 03:51:18 | amiller: | because they never received the data, and the miners who had it forgot it |
| 03:51:25 | petertodd: | yup, ugly problem! |
| 03:51:44 | amiller: | okay i'm about to give up again for tonight |
| 03:51:45 | petertodd: | proof of data posession seems to be 100% required for this stuff |
| 03:51:50 | petertodd: | same here |
| 03:51:57 | amiller: | this is an interesting area to go through but it seems to all be relegated to like |
| 03:52:16 | amiller: | "what happens when you relax the assumption/requirement that *everyone* gets to receive *all* the data in the blockchain" |
| 03:52:43 | petertodd: | I think that's 100% what it is - the question is simply one of how exactly does that relaxation occure |
| 03:52:44 | amiller: | 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:51 | amiller: | ok good |
| 03:53:59 | amiller: | 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:44 | petertodd: | 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:35 | amiller: | 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:18 | petertodd: | 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:06 | amiller: | there's a clear notion of "full nodes" and everything else |
| 03:57:19 | petertodd: | I don't agree with that! |
| 03:57:24 | amiller: | actually for my purpose i am defining full node as seeing and validating every transaction |
| 03:57:26 | Taek: | 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:32 | Taek: | because the latter would seem to be necessary |
| 03:57:47 | amiller: | full (validating) node the "validating" there is implicit |
| 03:58:09 | Taek: | *all the blocks that have been mined |
| 03:58:24 | petertodd: | well, its' kinda late, but ask me again later about partial UTXO set nodes |
| 03:58:32 | petertodd: | later |
| 03:58:49 | amiller: | yeah i know all about those |
| 03:58:55 | amiller: | thanks for the discussion |
| 04:01:48 | andytoshi: | 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:19 | andytoshi: | gmaxwell: plus the mechanics of ecdsa are totally irrelevant to bitcoin |
| 04:03:40 | andytoshi: | 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:53 | Emcy: | 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:28 | kanzure: | and commerce control laws |
| 05:01:20 | gmaxwell: | amiller: you recursively prove. |
| 05:01:53 | gmaxwell: | "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:09 | kanzure: | 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:20 | kanzure: | or the circumstances where that is definitely not achievable, for that matter. |
| 05:03:51 | andytoshi: | well, "definitely not achievable" would only be in case of an impossibility proof.. |
| 05:06:53 | kanzure: | but just an impossibility proof of that particular type of modeling |
| 05:46:15 | lechuga_: | i wonder why no1 has built a true universal p2p protocol |
| 05:47:14 | lechuga_: | fully nat traversing w/encryption + namecoin style dyndyns.org-ish name resolution |
| 05:49:13 | lechuga_: | onion routed |
| 06:22:03 | myeaglef1ies: | myeaglef1ies is now known as myeagleflies |
| 06:25:55 | Luke-Jr: | lechuga_: sounds like tor? |
| 06:26:02 | Luke-Jr: | or you mean without the directories? |
| 08:05:15 | wolfe.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:15 | wolfe.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:15 | wolfe.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:15 | wolfe.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:15 | wolfe.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:44 | davidlatapie: | davidlatapie has left #bitcoin-wizards |
| 09:15:13 | davidlatapie: | davidlatapie has left #bitcoin-wizards |
| 09:26:15 | gmaxwell: | andytoshi: I still don't get why people keep posting microscopic scale overviews that realy convey no understanding at all. |
| 09:26:42 | gmaxwell: | it's not just that one. there are a several others with almost identical content. |
| 09:27:32 | gmaxwell: | 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:55 | gmaxwell: | 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:41 | gwillen: | 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:54 | gwillen: | I say, as someone who doesn't really understand why it works over a finite field |
| 09:34:14 | gwillen: | (and by the reals I mean the real projective plane, IIRC) |
| 09:35:16 | gmaxwell: | 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:26 | gwillen: | ahhh, *nods* |
| 09:36:17 | gmaxwell: | 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:23 | gwillen: | * gwillen nods |
| 09:36:38 | gwillen: | in fact, a basic understanding probably gets you a broken implementation |
| 09:36:52 | gwillen: | at the least it gets you one with severe timing attack issues |
| 09:36:54 | gmaxwell: | yea, actually for the kinds of curves we use they absolutely will. |
| 09:37:44 | gmaxwell: | 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:51 | gwillen: | right |
| 09:37:55 | gwillen: | so if you miss the special case you lose |
| 09:37:59 | gwillen: | and if you don't miss it, you lose on timing |
| 09:38:22 | gmaxwell: | 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:27 | gwillen: | heh. |
| 09:38:44 | gwillen: | not quite as bad, given the current ssl CVE |
| 09:39:27 | gmaxwell: | 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:57 | gmaxwell: | is pretty useful though... even knowing nothing about implementing the group. |
| 09:40:01 | gwillen: | "understanding the hardness of discrete log" seems like an open problem, since proving the hardness of discrete log is an open problem ;-) |
| 09:40:11 | gwillen: | * gwillen nods |
| 09:40:28 | hearn: | by the time everyone is fully up to speed with ecc and related algorithms, it'll be time to switch to lwe :) |
| 09:40:59 | gmaxwell: | 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:08 | gwillen: | * gwillen nods |
| 09:41:43 | gwillen: | 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:49 | gwillen: | I hear djb has an entire website about this. |
| 09:42:13 | gmaxwell: | He does, I'm a little unhappy with it. Surprise: the only good curves are his. |
| 09:42:17 | gwillen: | hahahahaha. |
| 09:42:35 | gwillen: | well, if you've ever been acquainted with the djb koolaid before, you kind of know how the story goes |
| 09:42:58 | gwillen: | his koolaid is generally quite good as long as you can tolerate it... ;-) |
| 09:43:26 | gwillen: | but it doesn't shock me that his criteria happen to be the ones that pick out his curves |
| 09:43:36 | gwillen: | since he probably already had them in mind, unpublished, when picking those curves in the first place |
| 09:43:36 | gmaxwell: | 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:53 | gmaxwell: | gwillen: other way around. |
| 09:44:06 | gwillen: | well, I'm trying to give him the benefit of the doubt here :-P |
| 09:44:33 | gwillen: | I think he's more reasonable than to literally pick his criteria based on his own curves |
| 09:45:01 | gwillen: | I can totally believe he would call the ones his own curves fulfill more important than the ones they don't |
| 09:45:27 | gwillen: | anyway, I'm sympathetic to both sides on 'criteria that mostly nobody cares about, except when you do' |
| 09:46:19 | gwillen: | 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:38 | gmaxwell: | 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:44 | gmaxwell: | ... 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:00 | gwillen: | * gwillen nods |
| 09:47:11 | gmaxwell: | and well meaning concerned people posting on bitcointalk "omg secp256k1 is unsafe" |
| 09:47:13 | gwillen: | that's kind of unfortunate since I don't have the background to spot it |
| 09:47:19 | gwillen: | (I mean, from my perspective) |
| 09:47:32 | gwillen: | good to know I guess |
| 09:49:55 | davidlatapie_: | davidlatapie_ has left #bitcoin-wizards |
| 09:50:01 | gmaxwell: | 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:07 | gmaxwell: | ... parameters that yield a usable curve with that speedup trick available. |
| 09:51:15 | gmaxwell: | (that requirement plus that it be a group of prime order and the selection of the underlying field uniquely selects secp256k1 alone) |
| 09:51:25 | gwillen: | huh |
| 09:52:20 | gmaxwell: | 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:46 | gwillen: | * gwillen nods |
| 09:53:57 | gwillen: | "performant security" :-) |
| 09:54:32 | gmaxwell: | It's a good criteria in general. |
| 09:59:29 | gmaxwell: | 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:25 | gwillen: | * gwillen nods |
| 10:01:58 | gmaxwell: | in any case, I've already whined at djb some and he changed the page some, which is good. |
| 10:02:20 | gwillen: | haha, I'm both amazed and pleased that he listened |
| 10:02:44 | gmaxwell: | He sounded like he was blowing me off completely, I was surprised that he changed the pages. |
| 10:03:00 | gwillen: | what'd he change? |
| 10:05:06 | gmaxwell: | 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:12 | gmaxwell: | ... 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:31 | gwillen: | * gwillen nods |
| 10:05:38 | gmaxwell: | (rigid = means you had limited freedom in picking the parametrs to hide backdoors) |
| 10:05:59 | gwillen: | right |
| 10:06:01 | gwillen: | interesting |
| 10:06:06 | gmaxwell: | (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:24 | gmaxwell: | 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:07:47 | gwillen: | secg? |
| 10:08:11 | gwillen: | (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:19 | gmaxwell: | just one. |
| 10:08:29 | gwillen: | * gwillen nods |
| 10:09:35 | gmaxwell: | gwillen: standards group that published secp256k1 |
| 10:09:42 | gwillen: | ahh, *nods* |
| 12:05:49 | hearn__: | hearn__ is now known as hearn |
| 12:27:14 | andytoshi: | gmaxwell: hmm, i guess i have seen basically that article many times ... i think it was even in AA's book |
| 12:27:53 | andytoshi: | 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:04 | andytoshi: | and want to share that "insight" |
| 13:01:58 | Aquent: | Aquent is now known as winteriscoming |
| 14:28:28 | c0rw1n_: | c0rw1n_ is now known as c0rw1n |
| 15:13:07 | winteriscoming: | winteriscoming is now known as mooniscoming |
| 15:20:43 | mooniscoming: | mooniscoming is now known as Aquent |
| 17:19:40 | gmaxwell: | 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:26 | gmaxwell: | 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:10 | gmaxwell: | 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:54 | gmaxwell: | 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:20 | gmaxwell: | and so this way you can get "you need speak to only one honest peer" without a commitment in the blockchain. |
| 17:31:33 | gmaxwell: | 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:44 | amiller: | gmaxwell, have you seen versum |
| 17:31:50 | amiller: | http://people.csail.mit.edu/nickolai/papers/vandenhooff-versum.pdf |
| 17:33:54 | gmaxwell: | 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:48 | amiller: | i think versum is great, i wish i had thought of it |
| 18:12:21 | amiller: | 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:40 | amiller: | but i want to make a version of versum for my lambda-auth generic merkle tree language |
| 18:13:54 | gmaxwell: | I am very much not interested in "account balances" myself. |
| 18:21:55 | gmaxwell: | 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:29 | jgarzik: | gmaxwell, interesting |
| 18:23:36 | jgarzik: | RE moxiebox |
| 18:25:28 | gmaxwell: | 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:04 | gmaxwell: | 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:13 | jgarzik: | 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:13 | jgarzik: | for the most likely case, a quickly discover-able disagreement. |
| 18:33:48 | gmaxwell: | 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:02 | gmaxwell: | (obviously this requires completely determinstic computation) |
| 18:43:00 | woah: | would it ever be feasible to mine human readable public key hashes? |
| 18:58:04 | lnovyz: | lnovyz is now known as lnovy |
| 22:07:56 | SDCDev: | SDCDev is now known as somerandomguy332 |
| 22:08:18 | somerandomguy332: | somerandomguy332 is now known as SDCDev |