sipa changed the topic of #bitcoin-wizards to: This channel 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
weez17 has quit [Remote host closed the connection]
weez17 has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 265 seconds]
an4s has joined #bitcoin-wizards
<an4s>
Hi, what are some good resources to learn about information propagation in the Bitcoin network?
<bsm117532>
"The second one is to add an uncle mechanism or DAG structure to the share chain. This would likely be much fairer, but it would require a p2pool hard fork and a substantial amount of new code. This would be the best option if developer time weren't an issue."
RaV3N has quit [Ping timeout: 260 seconds]
<bsm117532>
So from everything I read, the orphan share problem is the most serious thing killing p2pool... belcher's concerns about large coinbases are real, but not showing up at the small hashrate p2pool has right now.
RaV3N has joined #bitcoin-wizards
<BlueMatt>
bsm117532: the issue was often lack of communication
<bsm117532>
Are we talking people communication or node/sharechain communication?
<BlueMatt>
bsm117532: people would be getting perfectly acceptable DOA rates (which may be valid bitcoin blocks that pay you out), while comparing those to pools where "stale" rates never pay you out
<BlueMatt>
the issue in p2pool was what your DOA rate was *compared to others*, not the absolute value
<BlueMatt>
but miners compared their absolute value to what other pools gave them anyway
<bsm117532>
For clarity, a DOA is a sharechain orphan, correct?
<BlueMatt>
oh, I never saw it that high, was always more like a few %
<BlueMatt>
maybe 5
an4s has quit [Ping timeout: 268 seconds]
<bsm117532>
That was kind of my interpretation the last time that I looked at this...that people were misunderstanding how p2pool worked.
<bsm117532>
The name "DOA" certainly doesn't help
<BlueMatt>
yea, I mean it was a combination of things, that was a big part of it
Newyorkadam has quit [Ping timeout: 264 seconds]
<BlueMatt>
ofc i doubt it'd've worked well across the gfw
<BlueMatt>
but it was never populat enough by the time mining got bit in china to ever find out
<BlueMatt>
there was some concept of auto-partiioning the network
<BlueMatt>
into multiple p2pools
<bsm117532>
I'm trying to nail down exactly what the technical problems with p2pool are. Communications problems suck, maybe a new p2pool can dump the bad history mojo...
<BlueMatt>
honestly I'm much more a fan of the centralized-pool-decentraized-transaction-selection model
nuncanada has quit [Ping timeout: 264 seconds]
<BlueMatt>
but maybe thats just cause we all got burned by p2pool adoption
Noldorin has joined #bitcoin-wizards
<bsm117532>
That's the BIP draft you posted above?
<BlueMatt>
yes
<bsm117532>
Yeah :-/
<BlueMatt>
I have it implemented and all (even mined a few testnet blocks), the issue is hitting roadblocks trying to get anyone to want to deploy it
JackH_ has joined #bitcoin-wizards
<bsm117532>
Hey, if using a DAG worked for Iota, it can work for you!
<BlueMatt>
lololol
<BlueMatt>
clearly we need more marketing mumbojumbo then we can restart p2pool and win
<BlueMatt>
have a few pending changes to the bip/impls that I wanted to do before posting it but got distracted the last 2 or so weeks so havent touched it, sadly
<BlueMatt>
hmm, who knows anymore, may be that there's a bunch of miners in china or some shit so everyone's doa gets fucked
<BlueMatt>
also, iirc, those are just p2pool-backed pools
<BlueMatt>
ie they just stand up an instance of p2pool, change the donation address/%, and then tell people to use it
<BlueMatt>
it was very common for a wehile
<bsm117532>
I can understand why p2pool is dying. If I'm having this much trouble figuring it out...compared to just pointing my miner at a centralized pool...
<BlueMatt>
(cause it was trivial to do - p2pool has good support for swapping out the web interface)
<BlueMatt>
s/is dying/died long ago/
JackH has quit [Ping timeout: 265 seconds]
<BlueMatt>
does anyone seriously maintain it anymore?
<bsm117532>
Dunno, I'm trying to revive it with braids and lightning payouts.
<bsm117532>
Join #braidpool if you're interested
<BlueMatt>
hmm, that sounds fun
<BlueMatt>
can I convince you to deploy my already-built shit instead :p
<bsm117532>
Maybe. Will take me a bit to read it though :-P
<BlueMatt>
tl;dr: clients select transactions/work, pool just manages payout
<BlueMatt>
centralized, but not in ways the network cares about
<fltrz>
andytoshi, right, but I would prefer to first verify for myself if it actually is conditionally secure, then write out the paper and proof, and then possibly conditionally release it for crypto (a smart contract could run metamath to verify a theorem, which only works if I have a valid proof)
dx25 has joined #bitcoin-wizards
anstaend1g has quit [Ping timeout: 240 seconds]
<fltrz>
any objector disagreeing with the theorem can point out I should really be proving a slightly different theorem before pledging some amount to the contract
napo1eon has quit [Ping timeout: 260 seconds]
cryptojanitor has joined #bitcoin-wizards
<fltrz>
*unconditionally secure of course (still waking up)
<andytoshi>
i can't parse "conditionally release it for crypto" or "metamath"
<andytoshi>
but if you're suggesting people bet money on the security of your scheme then you ought to prove it secure
<fltrz>
no not betting, metamath is a minimalist verifier, a smart contract can run this algorithm in theory, such that it returns funds if I dont supply my system and proof after a deadline, or forwards them to me if I do and the unconditional security is proven
<fltrz>
metamath.org (the 'meta' is not in the same sense as for example metaphysics, but in the sense of a metalanguage, a formal language (that the verifier can parse) describing a formal language or formal system (i.e. the axioms, theorems, proofs of a user)
<fltrz>
i.e. mathematics has neutral arbiters (not for axioms but for proofs)
<kanzure>
by 'betting' he means, before you tell people to use your stuff in production :)
merlinsbeard has quit [Quit: Leaving.]
<andytoshi>
very little crypto can be formally proven these days, the security games do not map well into formal models
<fltrz>
andytoshi, right, but unconditional security is much easier to Define
<fltrz>
imagine one-time-pads were not invented yet, if you came up with it, it is trivial for you to prove that if alice and bob share a secret OTP, they can encode a message (up to the size of the OTP), and Eve provably can not decode .. each decoding is equally possible
<fltrz>
this is 'information theoretic security', even if Eve has quantum computers running for 10^100 times the age of the universe, she can't decode the OTP encoded message
<fltrz>
as opposed to 'hardness security' where the hardness of one problem is proven to be at least as hard as another problem
<andytoshi>
yes, understood, but for any type of cryptosystem there is basically only one scheme that satisfies this
<fltrz>
but with enough computation time, most hardness problems can be solved, i.e. we have deterministic factorization algorithms, we just lack time
<fltrz>
what I seem to have come up with looks like 'information theoretically secure'/'unconditionally secure' secret key agreement over a public channel
<fltrz>
but I have not yet proven it
<andytoshi>
i don't believe you :P
<fltrz>
I fully agree, that's why I should use a neutral arbiter (like metamath) in a smart contract
<andytoshi>
but i am not aware of any impossiblitiy results that would prevent this
<andytoshi>
no, you should just prove it
<fltrz>
this way you are guaranteed your money back
itsme has joined #bitcoin-wizards
<fltrz>
you mean I should just publish it for free? then go back and work labour in the factory? nice
<andytoshi>
normal cryptographers publish results, yes
<andytoshi>
instead of doing this bizarre oraclized "i swear it's secure but i won't tell you the scheme" thing
<fltrz>
andytoshi, in my proposal, I can only get the funds if I publish the result to the smart contract (hence everyone)
<fltrz>
andytoshi, but I do intend to tell the scheme, I just want to secure a reward since I am an independent researcher
<fltrz>
or perhaps start running an ARG-turns-private-security-service
<fltrz>
:)
<fltrz>
andytoshi, one impossibility result that prevents this is the paper I mentioned before, but as I said, I have a hard time gauging how accepted the result is
<fltrz>
the paper does rest on a couple of unproven assumptions though
<andytoshi>
it doesn't matter "how accepted it is", either it applies and your result is wrong, or it doesn't and it's irrelevant. or it applies, your scheme is nonetheless secure, but their assumptions are wrong, which would also be novel
oleganza has joined #bitcoin-wizards
<andytoshi>
and in any case nobody is going to extract a theorem from a smart contract
<andytoshi>
so if you want anyone to read it you need to publish it normally
<fltrz>
what would extraction from a theorem mean? the theorem would be public
<fltrz>
the theorem would be the mathematical equivalent of "there exists a cryptosystem such that Alice and Bob can end up agreeing on a secret key, while only communicating over a public channel which Eve can overhear, with unconditional security"
<andytoshi>
and you think you can constructively prove this, and make a zero-knowledge proof of the proof's validity?
<andytoshi>
well, even using an oracle in place of the zkp would be interesting
<andytoshi>
but i think that'd be intractable
<fltrz>
I have no expertise in ZKP's (I know what they are), its the next cryptographic primitive I would try to find an unconditionally secure protocol for
<fltrz>
the proof is constructive yes, i.e. I don't leave the reader dangling with a "so its possible"
<fltrz>
but I have not checked the proof yet, all this 'how I sell it' is for later
<fltrz>
making the ARG might sell better
son0p has joined #bitcoin-wizards
<fltrz>
"very little crypto can be formally proven these days, the security games do not map well into formal models" yes and no: 1) the protocols assume an idealized attack model, i.e. the OTP can be broken if Eve can make a copy of one a pad, but then the assumption that A and B share a secret OTP is broken; similar for all sidechannel attacks
<fltrz>
2) most kinds of security do have very precise meanings like 'unconditionally secure' 'as hard as factorization' or assuming P!=NP
kenshi84_ has joined #bitcoin-wizards
<andytoshi>
if you can formalize even IND-CPA that would be an extremely interesting and novel result
<fltrz>
3) most papers and proofs work in English, and mathematicians refuse to formalize each and every step
<andytoshi>
it seems plausible that you coud do one-time IND-CPA, which is what the OTP satisfies. i'd look at the literature to see if this has been done
kenshi84 has quit [Ping timeout: 260 seconds]
<fltrz>
the information theoretic security proof for OTP is trivial
<fltrz>
you prove for one bit: first you prove that Bob s decoding of the ciphertext from Alice is equal to Alice's clear text, then you prove that Eve who only has the ciphertext, can not determine the OTP bit nor the plaintext bit
an4s has quit [Ping timeout: 256 seconds]
an4s has joined #bitcoin-wizards
daszorz has quit [Read error: Connection reset by peer]
<andytoshi>
1-time IND-CPA lets eve choose two messages and have bob encrypt one or the other, and eve has negligible advantage determining which one (in fact, zero advantage for the OTP)
<andytoshi>
which is equivalent to the standard result you are citing, in english
<andytoshi>
but in a formal language, that seems hard to show :)
<fltrz>
the way to prove the latter is to look at all possible combinations of the OTP bit and the clear text bit, if all states of the clear text bit can be paired with an OTP bit such that the ciphertext is identical, then the situations are indistinguishable for eve
<fltrz>
its not hard to formalize, the reason cryptographers don't is because they expect each other to read between the lines
<andytoshi>
what's your theory for why they go inventing things like cyclic security, citing the limitations of formal methods?
<fltrz>
while this is arguably OK for other fields of mathematics, I argue that for cryptography we should dumb down on each other and formalize the statements in machine readable format
thrmo has joined #bitcoin-wizards
<fltrz>
what is 'cyclic security' ?
<andytoshi>
https://eprint.iacr.org/2010/513 i'm amazed that you managed to read the formal methods in crypto literature so well to determine that it was trivial, and that people only weren't doing it out of laziness, and somehow never encountered this
<fltrz>
ask any cryptographer and he will say OTP's are trivially proven secure, what is not trivial is proving IND-CPA for an arbitrary encryption scheme
<fltrz>
the proof for one time pad is probably on its wikipedia page, since it is concise/trivial
napo1eon has joined #bitcoin-wizards
anstaendig has joined #bitcoin-wizards
<andytoshi>
i'm sure it will prove the specific simple property (unconditional hiding) that is satisfied by the OTP and only the OTP. it will not formalize 1-time IND-CPA in a machine-checkable way and show that OTP satisfies the formalized security property.
<fltrz>
? if a cryptosystem, say OTP claims to [given shared secret between Bob & Alice => Bob and Alice can send encryption over public channel which Eve overhears, such that for Eve each plaintext was equally possible] then I just need to prove that each plaintext was equally possible for Eve
<fltrz>
"each plaintext was equally possible" == information theoretic security, it does not matter how long in length or time your computer is
napo1eon has quit [Ping timeout: 255 seconds]
napo1eon has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 240 seconds]
str4d has quit [Ping timeout: 240 seconds]
Guyver2 has quit [Ping timeout: 260 seconds]
Guyver2 has joined #bitcoin-wizards
<fltrz>
andytoshi, the KDM security notion is for the specific case when Eve knows the plaintext to be say the secret key
son0p has quit [Remote host closed the connection]
<fltrz>
the only reason they put formal in quotes is to remind the reader that any theorem is only as applicable as its assumptions are held, ... any unmentioned sidechannels destroy the original constraint on the attack model
<fltrz>
one can also read their putting it in quotes as a criticism that we almost never truly formalize our theorems and belief systems
<andytoshi>
no, the history of KDM was that it came (in part) from frustrating fitting IND-CPA into formal methods
<andytoshi>
i'm not sure why you think cryptographers don't care about machine-checkable proofs
<andytoshi>
given that basically all of crypto is _about_ machine-checkable proofs (for another notion of 'proof')
<fltrz>
I think they *do* care
<fltrz>
just like we all think *the rest* should stand in line, *the rest* should fix global warming etc
<andytoshi>
…
<fltrz>
and as long as they don't offend one another they will partake in intellectual circle jerk
<fltrz>
i.e. not accuse each other of a lack of formalization
<andytoshi>
i think you need to spend many years working in cryptography and understanding the problems that working cryptographers care about before you'll have any hope of selling secret results
<fltrz>
I don't intend to sell secret results
<uiuc-slack3>
<stonecoldpat> rewards in cryptography come after publishing papers and surviving peer review, not before
TheoStorm has quit [Ping timeout: 240 seconds]
<fltrz>
that is the best one can do without objective proof verifiers
TheoStorm has joined #bitcoin-wizards
<waxwing>
would be fun to stick a bounty for a counterexample to fermat's last theorem on the blockchain tho' :)
<fltrz>
I would love it if such infrastructure was built and used
<fltrz>
(and I would have no qualms chipping in part of the bounty myself)
<waxwing>
admittedly the hash ones were a bit more interesting :)
Noldorin has joined #bitcoin-wizards
<fltrz>
uiuc-slack3, although even historically rewards in cryptography sometimes come before publishing papers and surviving peer review... the germans did not reward the allies for breaking their crypto, after reading the allies' published papers and the allies surviving german peer review...
oleganza has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
str4d has joined #bitcoin-wizards
<fltrz>
ugh reading the second paper, they juxtapose Formal view vs Computational view... formal has in my opinion always referred to the formal verification, i.e. mechanized computational verification. Any juxtaposition of Formal vs Computational in reference of 'proofs' merely indicates that pseudo-formal derivations have been foisted off as "formal" proofs when in fact they were not.
<fltrz>
so I still consider what I said at xx:25:33 to be correct
<fltrz>
a formal proof checker like metamath internally does little more than substitution of strings, i.e. purely computational
str4d has quit [Ping timeout: 268 seconds]
cryptojanitor has quit [Quit: Connection closed for inactivity]
napo1eon has quit [Ping timeout: 255 seconds]
itsme has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
napo1eon has joined #bitcoin-wizards
wxss has quit [Quit: leaving]
Samdney has quit [Ping timeout: 264 seconds]
meshcollider has joined #bitcoin-wizards
oleganza has joined #bitcoin-wizards
thrmo_ has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 240 seconds]
spinza has quit [Quit: Coyote finally caught up with me...]
spinza has joined #bitcoin-wizards
napo1eon has quit [Ping timeout: 260 seconds]
mn3monic has quit [Quit: Leaving]
thrmo_ is now known as thrmo
<uiuc-slack3>
<stonecoldpat> fltrz that is cryptanalysis :slightly_smiling_face: and motivates public encryption algorithms to be peer-reviewed before use