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
adnn has joined #bitcoin-wizards
Quanttek has quit [Ping timeout: 248 seconds]
laurentmt has joined #bitcoin-wizards
dansmith_btc has quit [Ping timeout: 250 seconds]
eudoxia has joined #bitcoin-wizards
r0ach has quit []
bityogi has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
dnaleor has quit [Quit: Leaving]
tromp_ has joined #bitcoin-wizards
wallet42 has quit [Read error: Connection reset by peer]
wallet42 has joined #bitcoin-wizards
wallet421 has joined #bitcoin-wizards
wallet42 has quit [Killed (adams.freenode.net (Nickname regained by services))]
wallet42 has joined #bitcoin-wizards
grandmaster has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
Dizzle has quit [Quit: Leaving...]
laurentmt has quit [Quit: laurentmt]
zooko has quit [Ping timeout: 272 seconds]
voxelot has quit [Ping timeout: 240 seconds]
dEBRUYNE_ has quit [Quit: Leaving]
roconnor has joined #bitcoin-wizards
brg444 has quit [Quit: Page closed]
rusty has quit [Ping timeout: 264 seconds]
DougieBot5000 has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 250 seconds]
wallet421 has joined #bitcoin-wizards
wallet42 is now known as Guest74347
wallet421 has joined #bitcoin-wizards
Guest74347 has quit [Killed (rajaniemi.freenode.net (Nickname regained by services))]
Starduster has quit [Read error: Connection reset by peer]
r0ach has joined #bitcoin-wizards
conner_ has joined #bitcoin-wizards
Howdy__ has joined #bitcoin-wizards
rustyn has quit [Read error: Connection reset by peer]
rustyn has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
c-cex-yuriy has quit [Quit: Connection closed for inactivity]
otoburb has quit [Quit: Changing server]
arowser has quit [Quit: No Ping reply in 180 seconds.]
arowser has joined #bitcoin-wizards
otoburb has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
justanot1eruser has joined #bitcoin-wizards
justanotheruser has quit [Read error: Connection reset by peer]
Giszmo has quit [Quit: Leaving.]
frankenmint has joined #bitcoin-wizards
voxelot has joined #bitcoin-wizards
Newyorkadam has quit [Quit: Newyorkadam]
mrkent_ has quit []
arowser has quit [Ping timeout: 252 seconds]
arowser has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 240 seconds]
TheSeven has quit [Ping timeout: 260 seconds]
contrapumpkin has joined #bitcoin-wizards
TheSeven has joined #bitcoin-wizards
[d__d] has quit [Remote host closed the connection]
[d__d] has joined #bitcoin-wizards
copumpkin has quit [Ping timeout: 240 seconds]
Newyorkadam has joined #bitcoin-wizards
justanot1eruser is now known as justanotheruser
justanotheruser has quit [Ping timeout: 245 seconds]
Newyorkadam has quit [Quit: Newyorkadam]
r0ach has quit []
Newyorkadam has joined #bitcoin-wizards
sparetire has quit [Quit: sparetire]
justanotheruser has joined #bitcoin-wizards
Jeremy_Rand_2_ has joined #bitcoin-wizards
Newyorkadam has quit [Quit: Newyorkadam]
nubbins` has quit [Quit: Quit]
Howdy__ has quit [Ping timeout: 240 seconds]
voxelot has quit [Ping timeout: 240 seconds]
Howdy__ has joined #bitcoin-wizards
FistfulOfCoin is now known as Fistful_of_Coins
Howdy__ has quit [Read error: Connection reset by peer]
r0ach has joined #bitcoin-wizards
p15x has joined #bitcoin-wizards
koshii has quit [Ping timeout: 272 seconds]
<fluffypony>
neat
<fluffypony>
thanks Aleph0
koshii has joined #bitcoin-wizards
Howdy__ has joined #bitcoin-wizards
chris13243 has joined #bitcoin-wizards
koshii has quit [Ping timeout: 264 seconds]
rustyn has quit [Read error: Connection reset by peer]
ThomasV has joined #bitcoin-wizards
Madars has quit [Ping timeout: 250 seconds]
rustyn has joined #bitcoin-wizards
OxADADA has quit [Ping timeout: 256 seconds]
davec has quit [Read error: Connection reset by peer]
OxADADA has joined #bitcoin-wizards
koshii has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
p15x has quit [Ping timeout: 250 seconds]
davec has joined #bitcoin-wizards
chris13243 has quit [Ping timeout: 252 seconds]
Madars has joined #bitcoin-wizards
tromp_ has quit [Remote host closed the connection]
koshii has quit [Ping timeout: 276 seconds]
MoALTz has joined #bitcoin-wizards
rusty has quit [Ping timeout: 250 seconds]
koshii has joined #bitcoin-wizards
chjj has quit [Ping timeout: 252 seconds]
p15x has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
liead has joined #bitcoin-wizards
adnn has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
roidster has quit [Ping timeout: 276 seconds]
paveljanik has quit [Ping timeout: 260 seconds]
ThomasV has quit [Ping timeout: 240 seconds]
tromp_ has joined #bitcoin-wizards
tromp_ has quit [Ping timeout: 260 seconds]
nuke1989 has quit [Read error: Connection reset by peer]
digitalmagus has joined #bitcoin-wizards
licnep has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
bit2017 has joined #bitcoin-wizards
koshii has quit [Ping timeout: 245 seconds]
gmaxwell has joined #bitcoin-wizards
<gmaxwell>
tromp: "(this also makes Cuckoo Cycle, unlike Hashcash, immune from Grover's quantum search algorithm)" not so-- the grover speedup is fully general and applies to any blockbox function.
GAit has quit [Quit: Leaving.]
gmaxwell has left #bitcoin-wizards [#bitcoin-wizards]
DougieBot5000 has quit [Quit: Leaving]
<nsh>
mm
<nsh>
grover's speedup is fully general, but any algorithm could be trivially tweaked to require more correlations to search than the current workable QCs, until such a time when the science/engineering makes QC scaleable to the same extent as classical logic, which may not even be possible in principle
<gwillen>
grover's usually doesn't matter asymptotically anyway
<gwillen>
you just have to double all your keylengths once
<gwillen>
(I hedge "usually" but I'm not aware of a case where it does matter)
* nsh
nods
koshii has joined #bitcoin-wizards
<nsh>
but i guess i'm suggesting you could write an algorithm that has a simple intermediary state blowup parameter that would expand beyond and feasible quantum computer
<nsh>
*any
<nsh>
but yeah, it's easier just to double keylength
<nsh>
(or security parameter)
grandmaster is now known as dansmith_btc
sCOGSBY has quit [Read error: Connection reset by peer]
damethos has joined #bitcoin-wizards
Howdy__ has quit [Ping timeout: 276 seconds]
markus-k has joined #bitcoin-wizards
adnn has quit [Remote host closed the connection]
adnn has joined #bitcoin-wizards
ThomasV has quit [Quit: Quitte]
Emcy_ has quit [Read error: Connection reset by peer]
markus-k has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
Howdy__ has joined #bitcoin-wizards
paveljanik has joined #bitcoin-wizards
paveljanik has quit [Client Quit]
<phantomcircuit>
gwillen, iirc the nsa thing referenced an improvement better than grover but i've no idea if that was serious or not
<gwillen>
yeah I dunno what that would be
<gwillen>
I'm aware of shor, which is significantly better than grover for factoring
<gwillen>
and there are other special-purpose quantum algorithms
<gwillen>
but they're hard to write and there are only a small number of original ones
andy-logbot has quit [Remote host closed the connection]
andy-logbot has joined #bitcoin-wizards
* andy-logbot
is logging
<nsh>
any superquadratic speedup would have to exploit [quite particular] problem space structural symmetries and would be very specific to a given algorithm
<yoleaux>
Shtetl-Optimized » Blog Archive » Quantum query complexity: the other shoe drops
<nsh>
so maybe that's a bit reductively-dogmatic, and we could be on the horizon of modest further polynomial-order separations between bounded-error quantum query complexity and deterministic query complexity
<nsh>
which is quite awesome and amazing but still nowhere near pathological
LeMiner has quit [Ping timeout: 246 seconds]
<nsh>
--
<nsh>
Flummoxing my expectations once again, Shalev produced the super-quadratic separation, but not by designing any new quantum algorithm. Instead, he cleverly engineered a Boolean function for which you can use a combination of Grover’s algorithm and the Forrelation algorithm (or any other quantum algorithm that gives a huge speedup for some partial Boolean function—Forrelation is just the maximal
<nsh>
example), to get an overall speedup that’s a little more than quadratic, while still keeping your Boolean function total.
<nsh>
I’ll let you read Shalev’s short paper for the details, but briefly, it once again uses the Göös et al. / Ambainis et al. trick of defining a Boolean function that equals 1 if and only if the input string contains some hidden substructure, and the hidden substructure also contains a pointer to a “certificate” that lets you quickly verify that the hidden substructure was indeed there.
<nsh>
You can use a super-fast algorithm—let’s say, a quantum algorithm designed for partial functions—to find the hidden substructure assuming it’s there. If you don’t find it, you can simply output 0. But if you do find it (or think you found it), then you can use the certificate, together with Grover’s algorithm, to confirm that you weren’t somehow misled, and that the substructure really
<nsh>
was there. This checking step ensures that the function remains total.
<nsh>
--
<nsh>
(ingenious)
ThomasV has joined #bitcoin-wizards
markus-k has joined #bitcoin-wizards
Quanttek has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
rusty has quit [Changing host]
rusty has joined #bitcoin-wizards
rusty has left #bitcoin-wizards [#bitcoin-wizards]
ThomasV has quit [Ping timeout: 250 seconds]
markus-k has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
r0ach has quit []
adnn has quit [Remote host closed the connection]
roconnor has quit [Ping timeout: 250 seconds]
Quanttek has quit [Ping timeout: 248 seconds]
supasonic has quit [Ping timeout: 264 seconds]
Starduster has joined #bitcoin-wizards
adnn has joined #bitcoin-wizards
licnep has quit [Quit: Connection closed for inactivity]
markus-k has joined #bitcoin-wizards
r0ach has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
markus-k has quit [Read error: Connection reset by peer]
markus-k has joined #bitcoin-wizards
c-cex-yuriy has joined #bitcoin-wizards
chjj has quit [Ping timeout: 240 seconds]
tromp_ has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
tromp_ has quit [Ping timeout: 252 seconds]
melvster has quit [Ping timeout: 240 seconds]
licnep has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
melvster has joined #bitcoin-wizards
chmod755 has joined #bitcoin-wizards
<waxwing>
quote from the princeton book: " Although it’s not used in Bitcoin, proof‐of‐stake is a legitimate alternate model and it’s used in other cryptocurrencies. "
dEBRUYNE has joined #bitcoin-wizards
<adlai>
those currencies are not insecure, they are "differently-secured"
<waxwing>
"Can virtual mining actually work?
<waxwing>
Virtual mining remains somewhat controversial in the mainstream
<waxwing>
Bitcoin community. There is an argument that security fundamentally requires burning real resources,
<waxwing>
solutions. If this argument is believed, then the apparent waste of the proof of work system can be
<waxwing>
requiring real computational hardware and expending real electrical power in order to find puzzle
<waxwing>
interpreted as the cost of the security that you get. But this argument hasn’t been proven, just as the
<waxwing>
security of virtual mining hasn’t been proven. "
<waxwing>
sorry that was a bit spammy; but it's from chapter 8, where they go into the topic in more detail.
adnn has quit [Remote host closed the connection]
laurentmt has quit [Quit: laurentmt]
<waxwing>
i find their position faintly ridiculous, personally, but there you go.
<adlai>
the insecurity of "virtual mining" does seem more of a game-theoretic "proof" than a cryptographic one
<phantomcircuit>
adlai, lol
<phantomcircuit>
amiller, what's up with the proof-of-stake thing?
Quanttek has joined #bitcoin-wizards
chmod755 has quit [Quit: Ex-Chat]
ThomasV has quit [Ping timeout: 240 seconds]
dnaleor has quit [Quit: Leaving]
dnaleor has joined #bitcoin-wizards
tromp_ has joined #bitcoin-wizards
tromp_ has quit [Ping timeout: 240 seconds]
ThomasV has joined #bitcoin-wizards
paveljanik has joined #bitcoin-wizards
Quanttek has quit [Remote host closed the connection]
Howdy__ has quit [Ping timeout: 240 seconds]
roidster has joined #bitcoin-wizards
roidster is now known as Guest65785
Guest65785 is now known as roidster
jtimon has joined #bitcoin-wizards
markus-k has quit [Read error: Connection reset by peer]
markus-k has joined #bitcoin-wizards
nabu has quit [Ping timeout: 245 seconds]
nabu has joined #bitcoin-wizards
markus-k has quit [Ping timeout: 264 seconds]
iddo has joined #bitcoin-wizards
atgreen has quit [Ping timeout: 250 seconds]
nabu has quit [Ping timeout: 245 seconds]
stevenroose has quit [Remote host closed the connection]
stevenroose|BNC is now known as stevenroose
stevenroose_ has joined #bitcoin-wizards
nabu has joined #bitcoin-wizards
stevenroose_ has quit [Client Quit]
stevenroose_ has joined #bitcoin-wizards
<Eliel_>
I'm finding it quite useful to think of a payment channel as a jointly managed wallet with mechanisms for ensuring neither party can take more than their own agreed on share of the coins. As well as a mechanism for updating the share ratio. Aside from that, as long as the parties cooperate, it seems to me it can function as a normal bitcoin wallet in addition to being a channel.
laurentmt has joined #bitcoin-wizards
<Eliel_>
I think you can even make regular transactions out of it without disruptions to the channel feature. Can someone confirm?
eudoxia has joined #bitcoin-wizards
nabu has quit [Ping timeout: 264 seconds]
<adlai>
Eliel_: this reframing is especially helpful when you can consider that the wallet can be 'denominated' (in the mind of the counterparties) in a different currency
<Eliel_>
adlai: can you explain what you mean?
dEBRUYNE_ has joined #bitcoin-wizards
<adlai>
"decentralized bitreserve"
nabu has joined #bitcoin-wizards
<Eliel_>
... oh, brilliant.
wasi has joined #bitcoin-wizards
tromp_ has joined #bitcoin-wizards
nubbins` has joined #bitcoin-wizards
nubbins` has quit [Client Quit]
<Eliel_>
adlai: although, is that part trustless? I can't figure out how to achieve that.
dEBRUYNE has quit [Ping timeout: 252 seconds]
<adlai>
if the counterparties disagree about the "price", worst case is that remaining funds are tied up until the refund thaws
<Eliel_>
ah right, you'd expect the parties to constantly update the closing transaction to match the price.
paveljanik has quit [Quit: Leaving]
<Eliel_>
adlai: I guess that can work with relatively small timeouts.
LeMiner has joined #bitcoin-wizards
tromp_ has quit [Remote host closed the connection]
ThomasV has quit [Quit: Quitte]
Giszmo has joined #bitcoin-wizards
eudoxia has quit [Ping timeout: 240 seconds]
p15x has quit [Ping timeout: 240 seconds]
dEBRUYNE_ has quit [Ping timeout: 276 seconds]
<tromp>
gmaxwell: quantum immunity refers to the looking for a cycle within one Cuckoo Cycle instance
licnep has quit [Quit: Connection closed for inactivity]
atgreen has joined #bitcoin-wizards
dEBRUYNE_ has joined #bitcoin-wizards
<nsh>
--
<nsh>
Abstract: In this paper we study and give the first detailed benchmarks on existing implementations of the secp256k1 elliptic curve used by at least hundreds of thousands of users in Bitcoin and other cryptocurrencies. Our implementation improves the state of the art by a factor of 2.5, with focus on the cases where side channel attacks are not a concern and a large quantity of RAM is available. As
<nsh>
a result, we are able to scan the Bitcoin blockchain for weak keys faster than any previous implementation. We also give some examples of passwords which have we have cracked, showing that brain wallets are not secure in practice even for quite complex passwords.
frankenmint has quit [Remote host closed the connection]
GAit has joined #bitcoin-wizards
<nsh>
their results with vanilla libsecp256k1 / i7-3520m 2.9Ghz / 4GB RAm / Windows 8 64bit: 47.2 us / pubkey generation
<nsh>
they claim 2.5x speedup with 1.09GB precomputation
<nsh>
(bonus hilarious list of cracked brainwallet keyphrases)
<instagibbs>
lol dajiahao, should have figured chinese phrases may be common
ThomasV has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 250 seconds]
tromp_ has joined #bitcoin-wizards
tromp_ has quit [Ping timeout: 240 seconds]
sparetire has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
zooko has joined #bitcoin-wizards
licnep has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
markus-k has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
bityogi has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
frankenmint has joined #bitcoin-wizards
rustyn has quit []
frankenmint has quit [Ping timeout: 272 seconds]
conner_ has quit [Remote host closed the connection]
jannes has quit [Ping timeout: 245 seconds]
damethos has quit [Quit: Bye]
conner_ has joined #bitcoin-wizards
melvster has quit [Ping timeout: 260 seconds]
dEBRUYNE_ has quit [Ping timeout: 252 seconds]
AaronvanW has joined #bitcoin-wizards
Starduster has quit [Ping timeout: 250 seconds]
voxelot has joined #bitcoin-wizards
nekrodesk has joined #bitcoin-wizards
melvster has joined #bitcoin-wizards
supasonic has joined #bitcoin-wizards
DougieBot5000 has joined #bitcoin-wizards
roman has joined #bitcoin-wizards
frankenmint has joined #bitcoin-wizards
frankenmint has quit [Ping timeout: 250 seconds]
dEBRUYNE has joined #bitcoin-wizards
digitalmagus has quit []
chmod755 has joined #bitcoin-wizards
wasi has quit [Quit: Leaving]
nekrodesk has quit [Max SendQ exceeded]
tromp_ has joined #bitcoin-wizards
tromp_ has quit [Ping timeout: 276 seconds]
catern has joined #bitcoin-wizards
zooko` has joined #bitcoin-wizards
<catern>
does anyone know any papers about applications of Bitcoin in networking, accounting for network resources? or applications of digital currencies in general to that?
zooko has quit [Ping timeout: 250 seconds]
<bsm117532>
catern: I just found joystream.co, which pays bittorrent seeders in bitcoin. Probably not what you're after though.
<catern>
interesting but I'm thinking more at the packet level
<bsm117532>
catern: What do you have in mind? Cryptographic verification is slow and data-intensive, I'd think it would be impossible to apply at the packet level. (e.g. a bitcoin transaction is similar in size to a TCP packet...)
* nsh
nods
<adlai>
bsm117532: if you have a channel open with your router, and they can construct the unsigned transaction incrementing by the cost of relaying your packet, all you really need to send across is the signature
<bsm117532>
adlai: If he's thinking about paying for bandwidth, I'm thinking the difficult part is cryptographically proving usage of bandwidth. OTOH if you're going to trust the router's measurement, a payment channel for bandwidth seems quite straightforward.
<instagibbs>
^^^ my thoughts too
conner_ has quit [Remote host closed the connection]
<kanzure>
huh now that i think about it, how do ISPs prove bandwidth utilization? do they just forego profo?
<kanzure>
*proof
Starduster has joined #bitcoin-wizards
<bsm117532>
kanzure: There is no proof.
<bsm117532>
kanzure: It's been known to be a problem if you get DDoS'ed...and get a huge bill...
<fluffypony>
why would they need to prove utilisation? you signed a contract that said they'll measure it and bill you.
<bsm117532>
I don't know what catern is after...I'm just thinking out loud... ;-)
<instagibbs>
fluffypony, i thought we were talking about routers as well...
<instagibbs>
like, along the way
<kanzure>
fluffypony: heh that's a classic scam :)
<fluffypony>
kanzure: I was just thinking that
<fluffypony>
just skim 10% on top of it
<fluffypony>
you'll make it back on overuse charges
<fluffypony>
if anyone complains, blame an error in the monitoring system and credit them, and then set the NOSCAM flag on their account
<instagibbs>
once we have paid-by-LN HORNET running on our routers, we should be good, right? :)
<kanzure>
i don't think that's enough, instagibbs
<instagibbs>
missed my /s tag
nekrodesk has joined #bitcoin-wizards
nekrodesk has quit [Max SendQ exceeded]
<instagibbs>
gotta put a space in irc /s
nibbler has quit [Remote host closed the connection]
nibbler has joined #bitcoin-wizards
<fluffypony>
yeah we need more names like HORNET
<fluffypony>
someone rename the Bitcoin PoW to OVERDRIVE, SHA-256 just isn't cutting it
<catern>
kanzure: i don't really know how ISPs prove bandwidth utilization either, the mechanism is probably something like "take a random sample of packets coming from customer link over time and add up their sizes"
<catern>
i always thought one of the big putative applications of digital currency in the 90s and early 00s was "we can use it to do accounting for network resources"
<phantomcircuit>
catern, have you seen the payment channels work?
<catern>
no but it doesn't really look relevant?
chmod755 has quit [Quit: Ex-Chat]
MoALTz__ has joined #bitcoin-wizards
MoALTz has quit [Ping timeout: 256 seconds]
MoALTz__ is now known as MoALTz
<bsm117532>
catern: With a payment channel you can pay incrementally as you use bandwidth, by passing signed transactions back and forth.
GAit has quit [Read error: Connection reset by peer]
GAit has joined #bitcoin-wizards
Dizzle has quit [Ping timeout: 260 seconds]
zooko` has quit [Ping timeout: 248 seconds]
chris13243 has joined #bitcoin-wizards
<catern>
what would have seemed more likely in retrospect to me is not a digital currency eventually being used for paying for packets, but rather network resource accounting methods eventually being used as a digital currency
roman has quit [Read error: Connection reset by peer]
roman has joined #bitcoin-wizards
supasonic has quit [Ping timeout: 250 seconds]
nibbler has quit [Remote host closed the connection]
nibbler has joined #bitcoin-wizards
zooko has joined #bitcoin-wizards
<fluffypony>
catern: so proof of bandwidth?
<catern>
no idea
conner_ has quit [Read error: Connection reset by peer]
<catern>
i'm just saying that the networking field has good incentives to come up with good useful resource accounting methods
conner_ has joined #bitcoin-wizards
<catern>
that work well
<catern>
because they have a direct application
<catern>
that work well between mutually distrustful users*
dnaleor has quit [Quit: Leaving]
<catern>
unfortunately i think networking today is all about going fast, and so "only use your fair share" is enforced by social pressure...
<catern>
(because enforcing it in hardware is slower than a naive router)
zooko has quit [Ping timeout: 250 seconds]
conner_ has quit [Remote host closed the connection]
zooko has joined #bitcoin-wizards
<bsm117532>
catern: But again the hard part is cryptographic proof of usage -- that's slow and difficult if not impossible to verify.
<catern>
oh, i don't know what technique exactly would be used
chris13243 has quit [Ping timeout: 240 seconds]
<catern>
just that if there was one that worked for networking accounting and actually got deployed for that purpose, it'd probably work as a general currency too