00:43:03	kanzure:	andytoshi: are there any proposals floating around for security-conscious integrated circuit manufacturing?
00:43:33	kanzure:	andytoshi: for example, circuit-level obfuscation that, when modified by the manufacturer, becomes obvious during program execution
00:44:02	kanzure:	or, circuit obfuscation that would take some amount of comptuational time to figure out here to hide the dopant trojans
00:44:06	kanzure:	*computational
00:44:12	gmaxwell:	so there are some papers where they can use precise timing to get high confidence that the circut is what you think it is... but these are still defeated by dopant flaws.
00:44:55	gmaxwell:	I've been thinking it would be interesting to use uniform combitoric logic (e.g. a FPGA) and then randomize the circuit you load... but kinda crazy power and space overhead.
00:45:00	kanzure:	dopant flaws require knowledge about where to insert the flaws, right?
00:45:14	gmaxwell:	right.
00:45:30	andytoshi:	kanzure: i don't know a think about it, in general "obfuscation" is synonymous with "secret crypto that is never published" tho :(
00:45:39	kanzure:	there might be generic dopant flaws that could be applied even in arbitrary circuits, but i'm at a loss for what to do about this
00:46:00	kanzure:	*generically-useful dopant flaws
00:46:11	andytoshi:	oh, i see, you are concerned about the designer being tricked by the mfg
00:46:22	andytoshi:	i was thinking, both are trying to prevent the user from modifying things
00:46:33	kanzure:	who is the user :)
00:47:18	gmaxwell:	kanzure: presumably my fpga notion could be narrowed to just have enough generality to implement a large number of possible circuits but not all...
00:47:19	kanzure:	i guess you could know about the class of generic dopant flaws, and attempt to test for that with precise timing tests
00:50:17	kanzure:	gmaxwell: so the worry is that the fpga manufacturer anticipated some of the circuits you would be loading up?
00:51:18	gmaxwell:	well the tradeoff is "use a FPGA" is probably sufficient unless the fpga maker knew your scheme in advance (e.g. and could reconize and replace your circuits in the loader)
00:51:35	gmaxwell:	but an FPGA is a rather extremely inefficient way to implement something.
00:52:16	kanzure:	well, inefficient solutions can be better than no solution heh
00:52:25	gmaxwell:	well if that works for you.
00:54:19	gmaxwell:	(esp since randomizing the circuit will have some large overhead too, at a minimum it will make the routing topology ugly)
00:55:15	kanzure:	"Obfusflow [Chakraborty and Bhunia, 2008] (and related follow-up work [Chakraborty and Bhunia, 2009]) is a method for preventing IP piracy. The general idea is to embed an authorization code in the hardware that can be turned on to convert the hardware from obfuscated mode — wherein functionality is broken — to normal mode. In order to get correct operation, the taped-out chip has to match a stored (on-chip) sequence of codes. If that ...
00:55:17	gmaxwell:	in any case, if your circuit is both randomized and uses voting, I think you can be very confident that no dopant flaws could be used.. though loader mischif would be harder.
00:55:21	kanzure:	... cannot be done, the behavior of the chip is essentially random, rendering it useless. The trade-off in this solution is area vs. anti-piracy (or anti-reverse-engineering) assurance because of the relatively high on-chip memory overheads"
00:55:54	kanzure:	(the anti-ip-piracy motivation is a little annoying, but i think their goals are the same)
00:56:45	gmaxwell:	(same kind of argument for anti-dopant would apply as does for the 'moonmathless ZKP' thing I posted)
01:01:45	kanzure:	is that voting between multiple implementations?
01:03:17	kanzure:	oh i forgot about http://diyhpl.us/~bryan/papers2/paperbot/Reversing%20Stealthy%20Dopant-Level%20Circuits.pdf
01:03:44	kanzure:	("use scanning electron microscopy and focused ion beams to get images of contact layers")
01:04:05	kanzure:	but that destroys the sample..
01:07:43	gmaxwell:	kanzure: the idea is that if you have a bag of circuits, and then you (unknown to the attacker) pool them randomly and then verify all the members of the pool disagree, it becomes very hard to make it such that a whole pool will be consistently wrong without having some partially wrong pools
02:47:57	sipa:	gmaxwell: have nodes for up to 5 or 6, for m-of-n with m>0 and n>6, and for "reference other node"
02:48:19	sipa:	gmaxwell: i have an encoding in mind
03:20:54	NikolaiToryzin_:	NikolaiToryzin_ is now known as NikolaiToryzin
03:33:50	NikolaiToryzin:	NikolaiToryzin is now known as AlexWagner
06:03:52	_0meta:	_0meta has left #bitcoin-wizards
08:04:31	gmaxwell:	sipa: how are you thinking of describing the fan-in. E.g. when you have a node with 5 or 6 inputs, ? .. hm. do you describe it backwards? e.g. a single bit out and a node that produces it, then just describe the input for every contributor?
08:05:17	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:17	wolfe.freenode.net:	Users on #bitcoin-wizards: andy-logbot cbeams arowser Starduster damethos AaronvanW comboy p15 irc88__ Happzz todaystomorrow x48 Dr-G2 pen jtimon copumpkin justanotheruser EasyAt fanquake wumpus coinheavy eristisk [7] [d__d] AlexWagner mortale hashtag emsid jgarzik nsh jaekwon dgenr8 K1773R devrandom Graftec koshii tromp__ jchp spinza waxwing coryfields xmj melvster go1111111 michagogo hollandais Guest36626 arubi _2539 postpre SDCDev altoz zenojis shesek mappum warren
08:05:17	wolfe.freenode.net:	Users on #bitcoin-wizards: jrayhawk jbenet LaptopZZ optimator_ pi07r Meeh Hunger-- Eliel poggy_ Luke-Jr Emcy_ Guest94465 kanzure danneu catcow TD-Linux Guest50253 helo smooth otoburb gwillen ryan-c nickler_ mmozeiko roasbeef pajarillo sl01 Keefe Dyaheon Grishnakh HaltingState rs0_ Gnosis nuke1989 ahmed_ZzZz wiretapped Muis artifexd Logicwax puszl nanotube espes__ andytoshi samson_ gavinandresen mkarrer rfreeman_w so zibbo lnovy dansmith_btc epscy tacotime LarsLarsen
08:05:18	wolfe.freenode.net:	Users on #bitcoin-wizards: OneFixt Fistful_of_coins BlueMatt Sangheili tromp wizkid057 a5m0 digitalmagus8 iddo starsoccer midnightmagic Adohgg berndj gribble Graet kinlo [Derek] pigeons BrainOverfl0w lianj_ Apocalyptic Iriez mr_burdell fluffypony bbrittain SomeoneWeird forrestv Anduck amiller Nightwolf Krellan BigBitz [\\\] Taek42 asoltys @ChanServ phedny petertodd burcin lechuga_ abc56889 Alanius Guest47516 throughnothing CodeShark harrow DoctorBTC gmaxwell
08:05:18	wolfe.freenode.net:	Users on #bitcoin-wizards: phantomcircuit HM crescendo nsh- bobke sipa
08:08:16	sipa:	gmaxwell: basically, yes
08:08:57	gmaxwell:	k. Sorry I didn't see how you were going to do it until the "hm" then it made sense to me. :)
08:09:06	sipa:	one way is having sort of an SSA form, where you give a list of expressions, and you're able to refer back to particular previous verious
08:09:10	sipa:	*variables
08:09:48	sipa:	i'm not sure that those very compact boolean networks are a good idea, anymore, though
08:10:04	sipa:	because they're very hard to introspect (... by a covenant, for example)
08:10:29	sipa:	i think you want to be able to enforce "the output script there has to enforce this property"
08:11:33	gmaxwell:	You can always require someone not use a feature though, so that wouldn't be the argument I'd use against them.
08:11:55	sipa:	fair point
08:12:55	sipa:	so, what i was thinking about (and it seems like it may be reasonable up to 5 inputs), is having nodes that not only encode the n-ary boolean function, but also its inputs
08:13:13	sipa:	and each input is allowed to be "true", "false" or "omitted"
08:14:47	gmaxwell:	I'd imagine the main point against them would be complexity vs space savings. Though if there is a simple tableish implementation of them the complexity may not be so bad... but the amount of space they can save over the worst case graph with just the and,or basis is bounded. (and even moreso with thresholds in the basis, since thresholds have bad depth as plain circuits over and,or)
08:14:56	gmaxwell:	sipa: what exactly is the implication of each of those states?
08:15:39	sipa:	the trues need to satisfy the predicate
08:15:56	sipa:	false or omitted are not evaluated
08:16:24	sipa:	for each omitted, there is a merkle hash
08:16:33	sipa:	for each true or false, there is a subexpression
08:16:43	gmaxwell:	oh and false would just be because its input is smaller than the hash that would replace it?
08:16:46	sipa:	yup
08:17:06	sipa:	which, together with deduplication, may be meaningful
08:17:34	gmaxwell:	hm, you mean refering to that subexpression elsewhere?
08:17:58	sipa:	for example, a checksig with a particular key could be referenced twice in the graph
08:18:10	sipa:	you'd rather give the actual checksig, and refer to it twice
08:18:16	sipa:	than give the merkle hash for it twice
08:18:21	gmaxwell:	(otherwise I was about to suggest than perhaps the length encoding for that subexpression could actually force it it to be <= the size of the hash)
08:18:58	sipa:	it may be overkill though
08:19:23	sipa:	only having given/omitted for each of the input may be easier
08:19:38	sipa:	and actual evaluate it
08:20:00	sipa:	but allow a checksig and falsechecksig, the latter of which is not evaluated, but does provide a hash
08:21:16	sipa:	for a&(b|c), the observation is that there are only 4 meaningful inputs: (true,true,false), (true,true,omitted), (true,false,true), (true,omitted,true)
08:21:54	sipa:	while the generic case with given/omitted for each input has 8 combinations
08:22:17	sipa:	hmm
08:22:49	gmaxwell:	hm, well you could first select which of the sensible satisfactions you're using, and then code which of the omitted ones you're giving explicitly anyways.
08:23:24	sipa:	yeah, false/omitted is just one bit per non-required input
08:25:04	gmaxwell:	even that could be omitted in a sufficently complex encoding, e.g. explore all the true paths first. then resolve references, then fill in any remaining omitted branches which weren't backwards filled.
08:25:44	sipa:	?
08:27:15	Happzz:	you guys don't justify what we pay you.
08:27:19	Happzz:	* Happzz hides
08:29:07	gmaxwell:	sipa: you signal true/omitted. but only give data along the true paths. Some of the data on true paths is references to prior subexpressions, which may be omitted ones (uh, with a constrant to avoid cycles).
08:29:32	gmaxwell:	if it was a true reference to an omitted one, you provide the subexpression then.
08:29:39	gmaxwell:	at the end anything that is still omitted gets its hash provided.
08:29:58	gmaxwell:	so there is no false vs omitted signaling, and no subexpression or subexpression hash is repeated.
08:30:47	gmaxwell:	and the 'true' signaling can be restricted to necessary and sufficent. E.g. a&&(b||c) needs to only code one truth bit (if b or c is the true path)
08:31:13	sipa:	yes, that's what i mean
08:31:21	sipa:	the false/omitted thing is a bit of a distraction
08:31:54	gmaxwell:	I'm just saying that it needs no signaling if the coding of hashes is defered until the end.
08:31:56	sipa:	but in the larger cases, the number of meaningful independent ways to satisfy the predicates isn't too much
09:01:47	Guest94465:	Guest94465 is now known as UukGoblin
09:19:36	fluffypony:	t
10:22:29	ahmed_ZzZz:	ahmed_ZzZz is now known as ahmed_uni
11:06:35	MRL-Relay:	[davidlatapie] Why a relay? Can't they just get there?
11:06:46	MRL-Relay:	[davidlatapie] Not that I am against it, just wondering
11:15:28	wumpus:	what is this relay?
11:16:04	fluffypony:	wumpus: Monero Research Lab
11:16:25	wumpus:	aha
13:21:35	Taek42:	Do you think there would be use for a lightweight blockchain that's primary purpose was a ledger
13:21:46	Taek42:	for example, currnetly when I update my system I contact a centralized size
13:22:02	Taek42:	but what if instead, I looked at a blockchain to figure out what version is the latest released
13:22:14	Taek42:	and that blockchain came from the dev's address or whatever
13:22:32	Taek42:	***the update transaction
13:23:00	andytoshi:	this is what git does
13:23:37	fluffypony:	and, if critical, the alert system can be used to notify people that a mandatory update is available
13:24:07	Taek42:	oh hmmm. I've never used git beyond github
13:25:40	stonecoldpat:	taek42: would it be based on a pow? Or just a chain of signatures ?
13:26:16	Taek42:	stonecoldpat it would still be pow. The idea is just to have a decentralized way of knowing when versions were released and which is the most recent
13:26:49	Taek42:	from wikipedia: "no canonical copy of the codebase exists by default, only working copies"
13:27:43	Taek42:	so you could use something like a blockchain to signal 'canonical' copies without needing a centralized source. Although I guess you could also just have a file in your repo that does the same thing.
13:29:09	stonecoldpat:	taek42: a pow may be over the top ? and you probably dont trust the majority of the world - just a select few in that type of system? (if its referring to latest code etc), i don't know how git works myself, but just a blockchain that iteratively has people signing each block, giving their approval for that release, may be useful?
13:30:07	stonecoldpat:	obviously the block with the most signatures would be part of the chain
13:31:15	Taek42:	well the idea isn't that you'd use one blockchain per software project, instead you'd have a single blockchain that documents all software projects. So, instead of going to gentoo.org to find the latest versions of stuff, I would just check my local copy of the software blockchain.
13:32:38	stonecoldpat:	taek42: just depends on the incentive for people to do the pow really, you could easily build it into of bitcoin and take advantage of the pow available. Put the software hash / details inside OP_RETURN and sign it from a well-known pubkey
13:33:03	stonecoldpat:	then the chain of transactions would be your blockchain, in a way
14:00:34	Eliel:	stonecoldpat: pow is useful for making it difficult to forge old release announcement even if the keys are stolen.
14:14:05	stonecoldpat:	Eliel: of course, that's why I said it depends on the incentive for people to do that - but you have the ultimate public bulletin board available with a pow that you wouldnt be able to match, i imagine you could have an spv client that follows a bitcoin address (software owner) - and this way you only receive transactions from that bitcoin address - which would make it very lightweight.
14:14:05	stonecoldpat:	(i'm just throwing out an idea, not that its the best, its probably not)
15:01:04	Eliel:	stonecoldpat: well, transactions do form a chain of hashes too.
17:30:55	sipa:	gmaxwell: schnorr verification in libsecp256k1 is 2-5% faster than ecdsa...
17:31:04	sipa:	i was hoping for more
17:31:29	sipa:	this is with GMP, which has very fast scalar operations (which is the largest difference between schnorr and ecdsa)
18:21:41	Dizzle__:	Dizzle__ is now known as Dizzle
20:00:55	andytoshi:	it may interest the crypto nerds here that "strong signature" is the standard term for what we have been calling "non-malleable", i.e. a sig for which an adversary cannot forge even for a message he has already seen a valid sig for
20:01:32	andytoshi:	so if you were trying to create a provably nonmalleable script-based signature scheme, you'd require any signature-of-knowledge opcodes to be strong signatures
20:02:03	Eliel:	finally looked up and read about schnorr signatures. It reminds me of the ring signature algorithm in cryptonote.
20:03:15	phantomcircuit:	andytoshi, malleable of course covers the entire tx
20:03:16	phantomcircuit:	but yes
20:04:55	andytoshi:	phantomcircuit: yeah, but we had been abusing terminology to refer to ecdsa itself as "malleable" which is not correct
20:05:10	andytoshi:	a literally malleable signature would let you modify the message out from under the sig
20:05:34	andytoshi:	Eliel: yes, a schnorr sig is the standard way to prove knowledge of a discrete logarithm
20:07:43	andytoshi:	it is a testament to how quickly crypto moves that that was patent-eligible at one point...today you could not get your name on such a simple idea
20:08:53	Eliel:	yes, it's a delightfully simple algo :)
20:11:04	justanotheruser:	Are sidechains redemptions probably going to require a bond that can be redeemed with someone who has created a fraud proof?
20:11:29	justanotheruser:	or is there going to be any method of directly incentivizing fraud proofs?
20:11:50	andytoshi:	well, fraud proofs are already incentivized by "if you don't make one your currency will be inflated by a thief"
20:12:11	andytoshi:	but there may need to be some sort of bond to deal with network fees
20:12:24	justanotheruser:	yeah
20:12:31	justanotheruser:	fraud proofs will not be free
20:12:53	andytoshi:	well, the proofs themselves could be free
20:13:06	justanotheruser:	there is a fee
20:13:09	andytoshi:	the problem is, if i post a sidechain transfer, pay a bunch of fees, then you prove it was fraudulent, how do you get the miner fees that i (the fraudster) have paid?
20:13:19	andytoshi:	justanotheruser: what fee?
20:13:30	justanotheruser:	andytoshi: transaction fee?
20:13:37	justanotheruser:	Or am I mistaking how a fraud proof would work
20:13:40	andytoshi:	the miners don't want inflation either
20:13:45	andytoshi:	they would let fraud proofs be posted for free
20:13:53	justanotheruser:	so they are paying the fee
20:14:28	andytoshi:	sure, if space is so limited that they are losing fees by including the reorg proof, they are eating that
20:21:51	Eliel:	of course, you could have a separate limit for valid fraud proofs
20:22:07	justanotheruser:	a separate limit?
20:22:48	justanotheruser:	also, there will need to be a decision to be made between blockchain bloat and utxo bloat, right? You can either keep the SPV proof information in the UTXO so it can be extended or you can do a new UTXO proof each time
20:23:08	justanotheruser:	s/UTXO proof/SPV proof
20:23:17	fluffypony:	we face that challenge with Monero - lots of conflation of "utxo bloat" with "blockchain bloat"
20:23:22	fluffypony:	when the two are no the same
20:23:35	andytoshi:	i think "new proof every time" is by far the simpler thing..
20:24:05	Eliel:	fluffypony: I thought utxo is a mostly useless concept with monero.
20:24:20	fluffypony:	Eliel: on the contrary, it's critical to the protoocl
20:24:22	fluffypony:	*protocol
20:24:24	andytoshi:	plus you generally favour blockchain bloat over utxo block whenever there is an option, the blockchain is stored by archival nodes while the utxo set must be stored by all full nodes
20:24:48	Eliel:	fluffypony: oh right, the key images?
20:24:51	fluffypony:	if you mix you do so with utxo's, and unless a utxo is spent at mixin 0 it remains a utxo forever
20:25:10	justanotheruser:	* justanotheruser wonders what the conversion rate is between utxo bloat and blockchain bloat
20:25:11	fluffypony:	no, key images are different, they're there to prevent obvious double-spends
20:26:39	fluffypony:	Eliel: in our 2.4gb-ish blockchain (physically, on disk) m_outputs (utxoset) is ~465mb, and m_spent_keys (key images) is ~266mb
20:26:43	Eliel:	fluffypony: ah right, you don't have an utxo set, you have a potential utxo set.
20:27:28	fluffypony:	Eliel: yes - well, or maybe more correctly "assumed-still-utxo set" ;)
21:55:27	Eliel:	is it safe to use the same k variable in multiple different signatures with schnorr signature?
21:55:49	gmaxwell:	no.
22:18:13	ahmed_uni:	ahmed_uni is now known as ahmed_
23:11:02	andytoshi:	Eliel: in both cases you are creating a line determined by your nonce and secret key (roughly, one is slope, the other y-intercept) as well as a point on this line determined by the message. because the map x -> xG is homomorphic from modular addition to group addition, by providing xG and kG you can allow others to verify the point is on this line, but the hardness of discrete log means they cannot
23:11:04	andytoshi:	determine the line itself
23:11:15	andytoshi:	but if you publish two points, that determines the line, and all your secrecy is in vain
23:32:01	x48_:	x48_ is now known as x48