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
thrmo has quit [Ping timeout: 240 seconds]
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 264 seconds]
belcher has joined #bitcoin-wizards
thrmo_ has quit [Quit: Waiting for .007]
satwo has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 256 seconds]
Giszmo has quit [Ping timeout: 265 seconds]
djhoulihan has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
CubicEarths has quit [Remote host closed the connection]
Giszmo has joined #bitcoin-wizards
CubicEarths has joined #bitcoin-wizards
CubicEarths has quit [Remote host closed the connection]
CubicEarths has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
CubicEarths has quit [Remote host closed the connection]
CubicEarths has joined #bitcoin-wizards
tromp has quit [Ping timeout: 248 seconds]
CubicEarths has quit [Ping timeout: 252 seconds]
Belkaar has quit [Read error: Connection reset by peer]
CubicEarths has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
Belkaar has quit [Read error: Connection reset by peer]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
AaronvanW has quit []
itsme__ has joined #bitcoin-wizards
itsme_ has quit [Ping timeout: 252 seconds]
victorSN has quit [Quit: Ping timeout (120 seconds)]
victorSN has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 256 seconds]
tromp has joined #bitcoin-wizards
fronti has quit [Ping timeout: 256 seconds]
comboy has quit [Remote host closed the connection]
fronti has joined #bitcoin-wizards
tromp has quit [Ping timeout: 268 seconds]
comboy has joined #bitcoin-wizards
Krellan has quit [Read error: Connection reset by peer]
Krellan has joined #bitcoin-wizards
kewde[m] has quit [*.net *.split]
kewde[m] has joined #bitcoin-wizards
ghost43 has quit [*.net *.split]
arubi has quit [*.net *.split]
intcat has quit [*.net *.split]
ghost43 has joined #bitcoin-wizards
intcat has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
betawaffle has quit [*.net *.split]
Belkaar has quit [Read error: Connection reset by peer]
kewde[m] has quit [Ping timeout: 240 seconds]
betawaffle has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 260 seconds]
bjorn[m] has quit [Ping timeout: 255 seconds]
victorSN has quit [*.net *.split]
contrapumpkin has quit [*.net *.split]
herzmeister[m] has quit [Ping timeout: 260 seconds]
azdrianz[m] has quit [Ping timeout: 256 seconds]
Jeremy_Rand[m] has quit [Ping timeout: 256 seconds]
contrapumpkin has joined #bitcoin-wizards
victorSN has joined #bitcoin-wizards
Dyaheon has joined #bitcoin-wizards
yoleaux has quit [Ping timeout: 240 seconds]
BashCo_ has quit [*.net *.split]
deusexbeer has quit [*.net *.split]
Lightsword has quit [*.net *.split]
gribble has quit [*.net *.split]
rodarmor has quit [*.net *.split]
maaku has quit [*.net *.split]
DougieBot5000 has quit [*.net *.split]
stiell has quit [*.net *.split]
sn0wmonster has quit [*.net *.split]
bildramer has quit [*.net *.split]
helo has quit [*.net *.split]
dgenr8 has quit [*.net *.split]
jonasschnelli has quit [*.net *.split]
windsok has quit [*.net *.split]
windsok has joined #bitcoin-wizards
jonasschnelli has joined #bitcoin-wizards
dgenr8 has joined #bitcoin-wizards
helo has joined #bitcoin-wizards
bildramer has joined #bitcoin-wizards
sn0wmonster has joined #bitcoin-wizards
DougieBot5000 has joined #bitcoin-wizards
stiell has joined #bitcoin-wizards
maaku has joined #bitcoin-wizards
Lightsword has joined #bitcoin-wizards
rodarmor has joined #bitcoin-wizards
gribble has joined #bitcoin-wizards
deusexbeer has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
d9b4bef9 has quit [*.net *.split]
kenshi84 has quit [*.net *.split]
jtimon has quit [*.net *.split]
murrayn has quit [*.net *.split]
phantomcircuit has quit [*.net *.split]
markus-k has quit [*.net *.split]
jnewbery has quit [*.net *.split]
adlai has quit [*.net *.split]
kallewoof has quit [*.net *.split]
MarcoFalke has quit [*.net *.split]
mdrollette has quit [*.net *.split]
spinza has quit [*.net *.split]
otoburb has quit [*.net *.split]
jcorgan has quit [*.net *.split]
modin has quit [*.net *.split]
fletom has quit [*.net *.split]
vdo has quit [*.net *.split]
phantomcircuit has joined #bitcoin-wizards
MarcoFalke has joined #bitcoin-wizards
jnewbery has joined #bitcoin-wizards
markus-k has joined #bitcoin-wizards
kallewoof has joined #bitcoin-wizards
mdrollette has joined #bitcoin-wizards
murrayn has joined #bitcoin-wizards
adlai has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
kenshi84 has joined #bitcoin-wizards
d9b4bef9 has joined #bitcoin-wizards
markus-k has quit [Max SendQ exceeded]
markus-k_ has joined #bitcoin-wizards
rodarmor has quit [Ping timeout: 245 seconds]
jcorgan has joined #bitcoin-wizards
modin has joined #bitcoin-wizards
fletom has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
vdo has joined #bitcoin-wizards
otoburb has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
rodarmor has joined #bitcoin-wizards
ChanServ has quit [*.net *.split]
itsme__ has quit [*.net *.split]
CubicEarths has quit [*.net *.split]
harrymm has quit [*.net *.split]
Nightw0lf has quit [*.net *.split]
a5m0 has quit [*.net *.split]
kabaum has quit [*.net *.split]
BCBot has quit [*.net *.split]
Anduck has quit [*.net *.split]
wizkid057 has quit [*.net *.split]
Giszmo has quit [*.net *.split]
berndj has quit [*.net *.split]
jrayhawk has quit [*.net *.split]
triazo has quit [*.net *.split]
davec has quit [*.net *.split]
achow101 has quit [*.net *.split]
gwillen has quit [*.net *.split]
uiuc-slack has quit [*.net *.split]
napo1eon has quit [*.net *.split]
devrandom has quit [*.net *.split]
roasbeef has quit [*.net *.split]
jaromil has quit [*.net *.split]
spinza has quit [*.net *.split]
otoburb has quit [*.net *.split]
jcorgan has quit [*.net *.split]
modin has quit [*.net *.split]
fletom has quit [*.net *.split]
vdo has quit [*.net *.split]
d9b4bef9 has quit [*.net *.split]
kenshi84 has quit [*.net *.split]
jtimon has quit [*.net *.split]
murrayn has quit [*.net *.split]
phantomcircuit has quit [*.net *.split]
jnewbery has quit [*.net *.split]
adlai has quit [*.net *.split]
kallewoof has quit [*.net *.split]
mdrollette has quit [*.net *.split]
MarcoFalke has quit [*.net *.split]
BashCo_ has quit [*.net *.split]
deusexbeer has quit [*.net *.split]
Lightsword has quit [*.net *.split]
gribble has quit [*.net *.split]
maaku has quit [*.net *.split]
DougieBot5000 has quit [*.net *.split]
stiell has quit [*.net *.split]
sn0wmonster has quit [*.net *.split]
helo has quit [*.net *.split]
bildramer has quit [*.net *.split]
dgenr8 has quit [*.net *.split]
jonasschnelli has quit [*.net *.split]
windsok has quit [*.net *.split]
victorSN has quit [*.net *.split]
contrapumpkin has quit [*.net *.split]
betawaffle has quit [*.net *.split]
ghost43 has quit [*.net *.split]
arubi has quit [*.net *.split]
intcat has quit [*.net *.split]
luke-jr has quit [*.net *.split]
Herka has quit [*.net *.split]
worstadmin has quit [*.net *.split]
mariorz has quit [*.net *.split]
Emzy has quit [*.net *.split]
NicolasDorier has quit [*.net *.split]
PsychoticBoy has quit [*.net *.split]
ThisAsYou has quit [*.net *.split]
Guest87695 has quit [*.net *.split]
mrd0ll4r has quit [*.net *.split]
Guest49421 has quit [*.net *.split]
adams__ has quit [*.net *.split]
wpalczynski has quit [*.net *.split]
jl2012 has quit [*.net *.split]
midnightmagic has quit [*.net *.split]
djhoulihan has quit [*.net *.split]
JackH has quit [*.net *.split]
Aesthetic has quit [*.net *.split]
Emcy has quit [*.net *.split]
harrigan has quit [*.net *.split]
bsm117532 has quit [*.net *.split]
molz has quit [*.net *.split]
Xantanium2 has quit [*.net *.split]
Madars has quit [*.net *.split]
Iriez has quit [*.net *.split]
Cory has quit [*.net *.split]
kanzure has quit [*.net *.split]
gnusha has quit [*.net *.split]
Gurgulor has quit [*.net *.split]
harding has quit [*.net *.split]
sipa has quit [*.net *.split]
aspect_ has quit [*.net *.split]
nejon has quit [*.net *.split]
runeks has quit [*.net *.split]
nikuhodai has quit [*.net *.split]
tuxcanfly has quit [*.net *.split]
morcos has quit [*.net *.split]
dlb76 has quit [*.net *.split]
yokwe has quit [*.net *.split]
aj has quit [*.net *.split]
mappum has quit [*.net *.split]
kisspunch has quit [*.net *.split]
Apocalyptic has quit [*.net *.split]
Varunram has quit [*.net *.split]
OhGodAGirl has quit [*.net *.split]
Guest77272 has quit [*.net *.split]
robmyers has quit [*.net *.split]
echonaut has quit [*.net *.split]
stevenroose has quit [*.net *.split]
gazab has quit [*.net *.split]
andytoshi has quit [*.net *.split]
comboy has quit [*.net *.split]
nephyrin has quit [*.net *.split]
gmaxwell has quit [*.net *.split]
fronti has quit [*.net *.split]
belcher has quit [*.net *.split]
zmanian has quit [*.net *.split]
eragmus has quit [*.net *.split]
suraeNoether has quit [*.net *.split]
wraithm has quit [*.net *.split]
cannedprimates has quit [*.net *.split]
bitjedi has quit [*.net *.split]
usecrypto has quit [*.net *.split]
markus-k_ has quit [*.net *.split]
ibrightly has quit [*.net *.split]
kinlo has quit [*.net *.split]
wallet42 has quit [*.net *.split]
rockhouse has quit [*.net *.split]
Eliel has quit [*.net *.split]
instagibbs has quit [*.net *.split]
espes has quit [*.net *.split]
nanotube has quit [*.net *.split]
ensign has quit [*.net *.split]
murchandamus has quit [*.net *.split]
fluffypony has quit [*.net *.split]
Guest7379 has quit [*.net *.split]
Guest69552 has quit [*.net *.split]
_whitelogger has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 276 seconds]
bjorn[m] has joined #bitcoin-wizards
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
itsme has joined #bitcoin-wizards
itsme__ has quit [Ping timeout: 252 seconds]
tromp has joined #bitcoin-wizards
herzmeister[m] has joined #bitcoin-wizards
kewde[m] has joined #bitcoin-wizards
Jeremy_Rand[m] has joined #bitcoin-wizards
azdrianz[m] has joined #bitcoin-wizards
tromp has quit [Ping timeout: 256 seconds]
Krellan has quit [Read error: Connection reset by peer]
<bsm117532>
I was just thinking of digging into bulletproofs. Because if you can prove the set of sequential statements y_1=x*x, y_2=y_1*y_1, y_3=y_2*y_2... then y_n=x^(2^n) and you can aggregate the proofs.
<bsm117532>
Which, ultimately, is something similar to bramc's idea, but hopefully faster than Snarks.
<bsm117532>
It seems like a lot of overhead to me. All I really want is for the prover to present x^(2^n) and for the verifier to have some way to verify or know 2^n.
ZmnSCPxj has joined #bitcoin-wizards
<ZmnSCPxj>
Good morning bsm117532, I believe what is commonly investigated, is that some entity first provides the timelock puzzle, the prover/grinder operates the timelock
<ZmnSCPxj>
When the timelock is completed, it yields a private key which the first entity has published the public key for (or encrypted some file using the public key for)
<ZmnSCPxj>
I do not know, what you want to use as X
<ZmnSCPxj>
How is X selected in your scheme?
<ZmnSCPxj>
One can argue that timelocks is what cryptocurrency mining *is*.
TheoStorm has quit [Remote host closed the connection]
<ZmnSCPxj>
Perhaps "chained hashing" in the gwern article would be of help.
<ZmnSCPxj>
For instance, we can get 256 x 32bytes random data from some public random source (e.g. the most recent block hash as seed for some PRNG)
<ZmnSCPxj>
The first 32-bytes, when hashed 64 (or however many) times, serves as the decryption key for the next 32-bytes.
<ZmnSCPxj>
the next 32-bytes, when hashed 64 times, serves as the decryption key for the next next 32-bytes.
<ZmnSCPxj>
and so on
<ZmnSCPxj>
the prover needs to execute all of those in sequence
TheoStorm has joined #bitcoin-wizards
<ZmnSCPxj>
And show the decryption key and the decrypted value for each 32-byte section of the original random data
<ZmnSCPxj>
the verifier(s) can perform the hashing in parallel, i.e. it checks the decrypted value for one 32-byte section, hashed 64 times, is the decryption key for the next 32-byte section
<ZmnSCPxj>
the verifier(s), with some probability, can sample only some of the hashes rather than the entire proof the prover provides
<ZmnSCPxj>
according to how much time it has in order to verify
ZmnSCPxj has quit [Quit: Page closed]
Emcy has quit [Ping timeout: 260 seconds]
<bsm117532>
ZmnSCPxj that's the usual way of doing timelocks. I'm doing something different. The prover presents a proof based on x which is derived from public data (e.g. using sha512 to map it into an elliptic curve point) and computes x^(2^n). Unlike the usual timelock puzzle, this is not created by a "challenger", and has no trusted setup.
Emcy has joined #bitcoin-wizards
<bsm117532>
This puzzle is a proof that a certain amount of time has elapsed since the public data x was revealed to the world (e.g. a block header)
ZmnSCPxj has joined #bitcoin-wizards
<ZmnSCPxj>
Yes, my latter proposal based on chained hashing should work for your application...?
<bsm117532>
Yes, it's just ugly. ;-) That's how bramc's proposal works, using a ZK-Snark to prove chained hashing.
<ZmnSCPxj>
I am almost certain that for some elliptic curve point X, X^(2^n) can be computed in O(1) time for all n.......
<bsm117532>
Parallel vs serial hashing only provides a constant-time speedup
<bsm117532>
x^2 can be computed in constant time. x^4 requires twice as much constant time ;-)
<ZmnSCPxj>
In the sub-second times you are measuring, perhaps constant-time speedup is sufficient?
<bsm117532>
Maybe. But I think we can do better
<ZmnSCPxj>
merkle trees?
<bsm117532>
That would work but they're large and I think the verifier still needs to recompute everything
<bsm117532>
There's also the problem that the verifier can't add this new block to his parents list until he's verified it, which is a significant amount of extra latency in the parallal-verification case
<ZmnSCPxj>
the verifier could probabilistically prove some subset of the entire proof
<ZmnSCPxj>
as long as the prover has no access to the RNG the verifier is using, the prover has to provide the entire proof anyway
<ZmnSCPxj>
and if there are multiple verifiers, then the prover can only fool some subsection of verifiers if it does not provide a correct entire proof
<bsm117532>
I'm not sure how the probabilities would work. I can present z=w^2 as a component which has nothing to do with the input x.
<ZmnSCPxj>
the verifier selects only some subsection of the proof to verify
<bsm117532>
Really there's only one relevant verifier, and it's the miner who builds on your block.
<bsm117532>
So an interactive proof? Using Fiat-Shamir? I've been thinking of that too...
<ZmnSCPxj>
not interactive, just a probabilistic one.
<ZmnSCPxj>
if you have verified the entire proof, then you know with certainty 1.0 that it is correct
<ZmnSCPxj>
if you have verified 0.5 of the entire proof, then you know with certainty (some complex mathematical formula) that it is correct
<bsm117532>
Well if I have a set of {y_i^2} and a bit-field from some entropy saying which ones I have to provide (common PRNG) I can do it.
<bsm117532>
Adds an O(n) space component, but I don't think that's a huge problem
<ZmnSCPxj>
Possibly, although I would prefer that the prover be required to provide the entire proof
<ZmnSCPxj>
the verifier uses some hidden entropy source to decide which parts of the proof to check
<bsm117532>
He would. For instance let the entropy for the proof be hash(x, x^(2^n)) for the solution n
<ZmnSCPxj>
which would improve the verification time compared to proving time
Chris_Stewart_5 has joined #bitcoin-wizards
<bsm117532>
Yes at the expense of a longer "finalization" phase once the prover has found his solution
<bsm117532>
I think with bulletproofs they can be incrementally aggregated
AaronvanW has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 252 seconds]
adrao has joined #bitcoin-wizards
adrao is now known as adra
<bsm117532>
The relevant metric for a good proof of time for this usage is (finalization time + verification time)/(mean block time).
adra is now known as adrao
<bsm117532>
With a braid the mean block time is expected to be 1-5 seconds or so.
<bsm117532>
Given recent advances in block propagation I'm expecting it to be closer to 1s.
<bsm117532>
bulletproofs range proofs take ~2ms to verify
AaronvanW has joined #bitcoin-wizards
<bsm117532>
Wait. Given that a polynomial y = x^(2^n) can be defined by 3 points on the curve, is there a way to present three points without the verifier having to recompute the curve?
dougsland has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 256 seconds]
harrymm has quit [Read error: Connection reset by peer]
harrymm has joined #bitcoin-wizards
jonasschnelli has quit [Excess Flood]
jonasschnelli has joined #bitcoin-wizards
jonasschnelli has quit [Changing host]
jonasschnelli has joined #bitcoin-wizards
<bsm117532>
No...this is the same as presenting x, x^(2^n)...
swagwise has quit [Ping timeout: 276 seconds]
djhoulihan has quit [Ping timeout: 260 seconds]
d9b4bef9 has quit [Remote host closed the connection]
jtimon has joined #bitcoin-wizards
dougsland has quit [Ping timeout: 265 seconds]
d9b4bef9 has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
Krellan has quit [Read error: Connection reset by peer]
Krellan has joined #bitcoin-wizards
djhoulihan has joined #bitcoin-wizards
swagwise has joined #bitcoin-wizards
djhoulihan has quit [Ping timeout: 240 seconds]
thrmo has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Quit: WeeChat 1.4]
Chris_Stewart_5 has joined #bitcoin-wizards
son0p has joined #bitcoin-wizards
satwo has joined #bitcoin-wizards
djhoulihan has joined #bitcoin-wizards
CubicEarths has joined #bitcoin-wizards
Krellan has quit [Read error: Connection reset by peer]
Krellan has joined #bitcoin-wizards
thrmo has quit [Quit: Waiting for .007]
SopaXorzTaker has quit [Remote host closed the connection]
SopaXorzTaker has joined #bitcoin-wizards
CheckDavid has joined #bitcoin-wizards
CubicEarths has quit [Remote host closed the connection]
SopaXorzTaker has quit [Remote host closed the connection]
SopaXorzTaker has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
Krellan has quit [Ping timeout: 265 seconds]
<swagwise>
Can I ask a question? I would be happy if anyone could answer me :)
<swagwise>
How are miners affected by increasing the block size to let's say 133 MB?
<swagwise>
Other than network latency and block propagation