wumpus changed the topic of #bitcoin-wizards to: This channel is is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
bendavenport has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 240 seconds]
Emcy_ has quit [Ping timeout: 272 seconds]
bendavenport has quit [Quit: bendavenport]
Emcy has joined #bitcoin-wizards
bedeho has quit [Ping timeout: 272 seconds]
roxtrong_ has quit [Remote host closed the connection]
Yoghur114 has quit [Remote host closed the connection]
<yoleaux>
kanzure: Sorry, that doesn't appear to be an HTML page.
<kanzure>
"Ideas for a new elliptic curve library"
CodeShark has quit [Ping timeout: 264 seconds]
phantomcircuit has joined #bitcoin-wizards
<katu>
sounds like a good idea overall. abuse operator overloading in lua or python for DSL scripts of curve definitions, make it emit appropiate C code
poppingtonic has joined #bitcoin-wizards
<gmaxwell>
katu: your signatures do not pass verification.
<katu>
gmaxwell: they dont? :(
<katu>
note that it has to be unmasked (while posshibly keeping the cofactor 8 constraints, ie keep lower 3 bits cleared, though not sure that is mandatory for this use)
<katu>
otherwise there is no commutativity necessary for the commitment to work.
paveljanik has quit [Quit: Leaving]
<gmaxwell>
I think you're mistaking the operation of curve25519(), it is not addition.
<katu>
let me write a PoC :)
Dizzle has quit [Quit: bbiab]
<gmaxwell>
What you're describing is this relation; (h()*(x-h()))G == xG which is clearly untrue.
ASTP001 has quit [Quit: ZZZzzz…]
StephenM347 has quit []
rusty has quit [Ping timeout: 240 seconds]
Jeremy_Rand_ has quit [Read error: Connection reset by peer]
nwilcox has joined #bitcoin-wizards
ASTP001 has joined #bitcoin-wizards
Jeremy_Rand_ has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
Guyver2 has quit [Quit: :)]
<katu>
gmaxwell: you're right, turns out they're only semi-commutative :(
<katu>
but curve25519(10, curve25519(20, G)) == curve25519(10, curve25519(10, curve25519(10, G))) does not
<katu>
oh well, now its obvious why its used only for dh
<gmaxwell>
katu: you can sign just fine with that function, though you need an additional add.
<katu>
yep
<katu>
larger signature
<gmaxwell>
katu: you're making a mistake of thinking the curve is "additive only" -- there is no such thing. (or rather, depending on how you define it, every curve is 'additive only')
<katu>
gmaxwell: by that i mean i cant supply multiplier modulo group order to "substract"
<gmaxwell>
you most certantly can.
<katu>
oh
* katu
had all the assumption about x-only 25519 wrong :)
<gmaxwell>
doesn't help that a lot of people (including DJB) explain things in a confusing manner.
OxADADA has joined #bitcoin-wizards
nwilcox has quit [Ping timeout: 264 seconds]
nwilcox has joined #bitcoin-wizards
bedeho has quit [Ping timeout: 265 seconds]
<phantomcircuit>
gmaxwell, a merkle sum tree could be implemented as a soft forking change today right?
<maaku>
phantomcircuit: i would be severely disappointed and lose faith in this process if something as uncontroversial as that didn't make it into whatever block size hard fork comes out of this
<katu>
it does modular inverse after each call to curve25519()
<phantomcircuit>
maaku, my interest is in whether the merkle sum trees could be soft forked in with a reasonable commitment scheme
<gmaxwell>
katu: you are computing 100*G on the lefthand side, and your right hand should be either 100G or 200*(1/2)G (or 3618502788666131106986593281521497120428558179689953803000975469142727125495G assuming the order you gave above is correct).
<maaku>
best non-fork: last 32 bytes of last output of coinbase. best soft-fork: last 32 bytes of last output of last transaction (soft-fork only needed to guarantee output is available for miner to spend). best hard-fork: right-branch from root of merkle tree (transactions left, commitments right)
poppingtonic has quit [Ping timeout: 244 seconds]
poppingtonic1 is now known as poppingtonic
<phantomcircuit>
maaku, actually im not sure that what i was thinking is even useful
<phantomcircuit>
i was thinking that you might be able to get the incentives right for utxo commitments with a sum tree, but actually im not sure you could
<phantomcircuit>
instead of inserting fake entires into the commitment an attacker can simply replace all the scriptPubKey's
bedeho has joined #bitcoin-wizards
<katu>
just for clarity (if theres any with treating 25519 as blackbox), gmaxwell, andytoshi :curve25519(2500, G) == curve25519(50, curve25519(50, G))
<katu>
curse you djb and your confusing explanations
moa has quit [Quit: Leaving.]
<CodeShark>
phantomcircuit: just got here - what are you trying to accomplish?
<CodeShark>
sum trees over outputs?
<CodeShark>
that do not require checking signatures?
<phantomcircuit>
CodeShark, sum tree over the utxo set commitment plus sum tree over the blocks would enable proving false inflation
<phantomcircuit>
but it doesn't help with proving that the utxo commitment has the right pubkey scripts
<CodeShark>
that would require checking signatures, no?
<CodeShark>
at the very least
<phantomcircuit>
replacing the pubkey scripts?
<phantomcircuit>
no because they can also give a fake txid:index pair
<phantomcircuit>
and now you need to prove that the txid:index doesn't appear in the blockchain
<CodeShark>
hence "at the very least" - you also need to prove the outputs are spendable
<CodeShark>
right
<CodeShark>
can we do better than O(n) for such a proof, n being the blockchain length?
<phantomcircuit>
i dont think so
<phantomcircuit>
well maybe we can with a hard fork
* phantomcircuit
goes to look something up
<andytoshi>
katu: that's correct. can you link to djb's explanation of this?
<phantomcircuit>
CodeShark, no i dont think you can
<katu>
andytoshi: 'ensure ``contributory'' behavior' ... just ^f contributory in http://cr.yp.to/ecdh.html
<phantomcircuit>
proving that a transaction traces back to a coinbase can be done in less than n but is hardly compact
<CodeShark>
you could do a probabilistic proof that fails on occasion, perhaps
<phantomcircuit>
but i dont see how you can prove that a transaction was never valid
<katu>
i'm curious now why ed25519 then (which uses y and conversion to jacobian representation, and is thus a bit more complicated)
<katu>
as it seems montgomery 25519 is ok for signing
<phantomcircuit>
CodeShark, im not sure a probabilistic proof is useful, probabilistic validation which generates absolute proofs are but not probabilistic proofs
<phantomcircuit>
:)
<phantomcircuit>
gmaxwell, am i missing something obvious?
<andytoshi>
katu: i'm confused what coordinates have to do with ECDH at all
<phantomcircuit>
(i ask because i know you've thought about fraud proofs a bunch)
<maaku>
phantomcircuit: fraud proofs are SPV security.
<maaku>
am I missing something? I'm not sure what you're aiming for
<CodeShark>
SPV = proof of existence of something with a certain amount of PoW?
<katu>
andytoshi: the two implementations (edwards vs montgomery), but montgomery only with x/z axis seems far simpler / faster to implement
<maaku>
SPV = "assume >50% hashrate is honest"
<maaku>
or perhaps more strictly "no single colluding carte with >50% hashrate"
<CodeShark>
hmmm - so SPV can also include proving that a UTXO does not exist given the assumption that >50% of hashrate is honest?
<maaku>
CodeShark: sure, have a proof against the commitment in the prior block
<phantomcircuit>
maaku, the goal is that fraud proofs can be provided by any full node not just the miners
<CodeShark>
and by "honest" we actually mean "actually validates the blocks it publishes and only publishes valid blocks" right?
<CodeShark>
we're ignoring block withholding attacks or other such things
<phantomcircuit>
maaku, consider that the incentives work because full nodes call bullshit if miners try to do anything pshishy, now consider how many people are using spv clients and what that does to the networks incentive model
<andytoshi>
katu: that page is really hard to understand.
<andytoshi>
i'm not certain what me means by "contributory behaviour", though i infer it somehow means "behaviour that does not involve sending low-order points", but his claim that this is irrelevant to DH i think is just wrong
<phantomcircuit>
maaku, i can see how to do a fraud proof with two utxo commitments and the block
<andytoshi>
oh, no, it's not wrong if you're just using the DH secret as a shared secret
<phantomcircuit>
which would be an improvement on spv
<phantomcircuit>
but is still not quite as strong as a full node
<andytoshi>
i don't know what it means for a protocol to be "unusual" either. the use of that word sounds like really non-adversarial thinking
justanotheruser has quit [Read error: Connection reset by peer]
<maaku>
I'm not sure I see the need to incentivise broadcasts of fraud proofs?
<maaku>
Pretty much everyone has an indirect incentive to share fraud proofs of candidate blocks.
justanotheruser has joined #bitcoin-wizards
<maaku>
Maybe I'm being dense.
<CodeShark>
tragedy of the commons
<CodeShark>
"I'll let someone else do that"
nwilcox has quit [Ping timeout: 256 seconds]
<CodeShark>
if that "someone else" is a very small number and it is possible to discover the identities, all sorts of potentially ugly scenarios are possible
nwilcox has joined #bitcoin-wizards
<maaku>
CodeShark: well in a probabalistic future presumably that's what everyone is doing.
<maaku>
checking some subset of the utxoset, and relaying fraud proofs
<maaku>
*probabalistic validation future
<phantomcircuit>
maaku, im more interested in making the fraud proofs as compact and complete as possible
<kanzure>
reducing the number of necessary fraud proof types is very useful thing to do
<phantomcircuit>
i dont see any way to prove that the entries in a utxo commitment have false indexes (if we assume someone is willing to get lots of hashing power to generate say 100 blocks in a row that build on the false commitments)
<phantomcircuit>
kanzure, unfortunately it seems like lots and lots are needed
<phantomcircuit>
bbl
AnoAnon has joined #bitcoin-wizards
AnoAnon has quit [Max SendQ exceeded]
<maaku>
phantomcircuit: the roots won't match, no?
<maaku>
phantomcircuit: it will come down to spending txid that doesn't exist in the prior commitment or something like that, and a full node could prove that it doesn't exist
<kanzure>
there have been some proposals that included a rolling window or pruning or something.. when you design the window to be too short/small, you open up various grinding attacks. not sure if this is what phantomcircuit was talking about.
shen_noe has quit [Quit: Leaving]
<gmaxwell>
andytoshi: the argument that it's unnecessary is that the low order points are few enough that you cannot use them to extract secret data.
ThomasV has quit [Ping timeout: 255 seconds]
<phantomcircuit>
maaku, that's right the roots won't match but to calculate the root you need to have the full block data between the commitments
<phantomcircuit>
if you can prove that the commitment is fake with less than the full block data between it and the previous commitment
<phantomcircuit>
then we're talking
<CodeShark>
by fake you mean "spends an output that either doesn't exist or has already been spent"?
<katu>
andytoshi: chance of hitting em is astronomically low assuming there's no external malleable factor (i suppose on has to be careful when compositing n-of-m signatures in ecschnorr)
<gmaxwell>
katu: the chance of hitting them is _1_ if someone sends you one.
erasmospunk has quit [Remote host closed the connection]
<gmaxwell>
Thats the same kind of incompetent reasoning that results in pratical vulnerabilities in other ECDH implementations; in this case it's okay (because you don't get enough choices of low order to learn much about the private key), but not because the chance of hitting them is low.
orik has joined #bitcoin-wizards
nwilcox has quit [Ping timeout: 250 seconds]
King_Rex has quit [Remote host closed the connection]
nwilcox has joined #bitcoin-wizards
nwilcox has quit [Ping timeout: 246 seconds]
nwilcox has joined #bitcoin-wizards
<phantomcircuit>
CodeShark, i specifically mean, replaces a valid entry in the UTXO with an invalid entry (thus preserving the merkle sum tree values)
<phantomcircuit>
for example
<phantomcircuit>
you have an entry which is a valid unspent outpoint and the correct amount and script pubkey
<phantomcircuit>
the attacker replaces that with a non existent outpoint (ie random txid) and the correct amount and the attackers script pubkey
<phantomcircuit>
you can prove they lied only be providing all of the blocks between the last utxo commitment and that block
eudoxia has joined #bitcoin-wizards
DougieBot5000 has quit [Quit: Leaving]
<phantomcircuit>
which isn't as good as a full node which trusts nothing
<phantomcircuit>
gavinand1esen, solve that and i wont oppose much larger blocks
<katu>
gmaxwell: yes, luckily djb gave quite clear instructions in that regard - "check your base point input that they're not a twist or trivial order generator"
<katu>
gmaxwell: or have i missed something and the pathological cases are not easy to detect (low 3 bits for twist, and 2 constants for the other small orders)
sipa has joined #bitcoin-wizards
<gmaxwell>
katu: what? that page _specifically_ tells you to do no verification of input points. (which is actually fine, but for other reasons)
<gmaxwell>
"How do I validate Curve25519 public keys?
<gmaxwell>
Don't. "
<katu>
gmaxwell: read further about the bit munging
<katu>
and what to do if you remove it
<gmaxwell>
katu: I'm not following your comments. The page is completely, blood flowing from eyes, clear.
<gmaxwell>
The only bit operations discussed on that page are related to secret key generation.
<phantomcircuit>
gmaxwell, i think if there was blood flowing from my eyes i'd have trouble seeing it too
* phantomcircuit
runs away
<sipa>
have you actually tried that?
<CodeShark>
you have blood vessels always right on your retina but you don't see them because the retina only senses changes
<sipa>
that is by no means equivalent to "blood flowing from eyes" :p
<CodeShark>
the blood vessels carry blood away from the eyes, so in a sense it is :p
<sipa>
ok, you win!
<CodeShark>
:)
<sipa>
arguable, in a very relevant way: if those vessels weren't pumping blood away, things on that page would go very unclear rapidly
<phantomcircuit>
sipa, i've actually gotten lots of fake bloof in my eyes before
<phantomcircuit>
0/10 would not recommend
nwilcox has quit [Ping timeout: 264 seconds]
nwilcox has joined #bitcoin-wizards
<katu>
gmaxwell: i mean the 'In those protocols, you should reject the 32-byte strings' part. i presume he's talking about public keys.
<katu>
gmaxwell: if you input 325606250916557431795983626356110631294008115727848805560023387167927233504 as public key (generator), you'll see order 8. this is presumably ok for DH, but not when it is abused for other uses.
<gmaxwell>
katu: you ___MUST___ reject low order points for ECDH generally; it just happens to be the case for curve25519 the particular selection of possible low order points is not a set that will cause trouble. But it is not generally true.
<gmaxwell>
(it works in this case because you only get points of order 8,4,2; and your key has been magicked to be a multiple of 8)
<gmaxwell>
but this is not something which is generally true for ECDH.
<gmaxwell>
And failing to validate points generally (outside of this specific setup), _for ecdh_ results in exploitable vulnerability when an attacker sends you points of many different orders and learns your key mod a collection of small primes and can recover the value via chinese remander theorem.
<katu>
gmaxwell: still, if both parties announce they have low order public point, hilarity ensues :)
<katu>
my point is, it makes no sense to do that
<katu>
of course this is all in context of 25519
licnep has quit [Quit: Connection closed for inactivity]
<tromp>
CRT is the attack i use on the order of legal Go positions:)
<gmaxwell>
tromp: I was mind blown with the go position counting stuff. So interesting that the combinitorics is simple enough to yield to analysis like that.
<gmaxwell>
katu: Just please take care to not generalize what works for one particlar set of parameters for other things.
<tromp>
in fact i should have finished the computation by now. were it not for the last 3 jobs all suffering fatal filesystem errors
<gmaxwell>
tromp: I'd seen the paper but I didn't connect that it was you.
<gwillen>
tromp: I love that we have the power to do it up to ONE less than the traditional go board size
<tromp>
still hope to finish by Xmas!
<gwillen>
+1
<gmaxwell>
next step should be a go board compression program that converts any legal goboard into a single integer on the range of [zero .. npositions) :)
bramc has joined #bitcoin-wizards
<gmaxwell>
tromp: I'd offer to help compute but I don't have any cpu farms with oodles of storage handy at the moment!
Jeremy_Rand_ has joined #bitcoin-wizards
Jeremy_Rand_ is now known as Jeremy_Rand
Jeremy_Rand has quit [Client Quit]
<tromp>
that's only saving about 6 bits on the std encoding:(
Jeremy_Rand has joined #bitcoin-wizards
<gmaxwell>
tromp: hahah
<tromp>
fortunately your tax dollars help (computation being done at IDA princeton)
rusty has joined #bitcoin-wizards
<poppingtonic>
+1
nwilcox has quit [Remote host closed the connection]