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
Alina-malina has quit [Ping timeout: 252 seconds]
Alina-malina has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
alpalp has quit [Ping timeout: 256 seconds]
alpalp has joined #bitcoin-wizards
bsm1175321 has quit [Quit: Leaving.]
bsm1175321 has joined #bitcoin-wizards
nooblord has joined #bitcoin-wizards
Dizzle has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy has quit [Ping timeout: 248 seconds]
CrazyLoaf has quit [Quit: Connection closed for inactivity]
AaronvanW has quit [Remote host closed the connection]
rusty has joined #bitcoin-wizards
<petertodd>
musalbas: yes, the underlying data structure certainely can do that, and IIRC it's implemented too
roconnor has quit [Ping timeout: 260 seconds]
rusty has left #bitcoin-wizards [#bitcoin-wizards]
CrazyLoaf has joined #bitcoin-wizards
Yogh_ has quit [Ping timeout: 250 seconds]
Yogh has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
chjj has quit [Ping timeout: 260 seconds]
wasi has quit [Ping timeout: 244 seconds]
DigiByteDev has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
wasi has joined #bitcoin-wizards
instagibbs has quit [Ping timeout: 265 seconds]
Tenhi has quit [Excess Flood]
Tenhi has joined #bitcoin-wizards
davec has quit [Read error: Connection reset by peer]
davec has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
Firescar96 has joined #bitcoin-wizards
Alopex has joined #bitcoin-wizards
alpalp has quit [Ping timeout: 245 seconds]
priidu has joined #bitcoin-wizards
Alina-malina has quit [Ping timeout: 256 seconds]
priidu has quit [Ping timeout: 252 seconds]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
WungFu has quit [Ping timeout: 250 seconds]
Burrito has quit [Quit: Leaving]
WungFu has joined #bitcoin-wizards
kkode has quit [Ping timeout: 256 seconds]
Firescar96 has quit [Ping timeout: 260 seconds]
roconnor has joined #bitcoin-wizards
nooblord has quit [Quit: Leaving]
pro has quit [Quit: Leaving]
alferz has quit [Ping timeout: 244 seconds]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
roughly27 has quit [Remote host closed the connection]
alferz has joined #bitcoin-wizards
alferz has quit [Changing host]
alferz has joined #bitcoin-wizards
wasi has quit [Excess Flood]
wasi has joined #bitcoin-wizards
alferz has quit [Ping timeout: 244 seconds]
WungFu has quit [Ping timeout: 252 seconds]
alferz has joined #bitcoin-wizards
Firescar96 has joined #bitcoin-wizards
aalex has quit [Ping timeout: 260 seconds]
aalex has joined #bitcoin-wizards
xissburg has quit [Ping timeout: 260 seconds]
Alina-malina has joined #bitcoin-wizards
CrazyLoaf has quit [Quit: Connection closed for inactivity]
<kanzure>
musalbas: so you claim that with a merbinner tree and consistency proofs, you can detect double spending, without knowing the transactions? or what is the claim more precisely.
harrymm has quit [Remote host closed the connection]
harrymm has joined #bitcoin-wizards
aalex has quit [Ping timeout: 256 seconds]
Ylbam has joined #bitcoin-wizards
aalex has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
nikivi has joined #bitcoin-wizards
Expanse is now known as nOgAnOo
Giszmo has joined #bitcoin-wizards
nOgAnOo has quit [Changing host]
nOgAnOo has joined #bitcoin-wizards
nOgAnOo has joined #bitcoin-wizards
roconnor has joined #bitcoin-wizards
Cory has joined #bitcoin-wizards
Cory has quit [Excess Flood]
Cory has joined #bitcoin-wizards
Cory has quit [Excess Flood]
Guest12765 has joined #bitcoin-wizards
Guest12765 has quit [Excess Flood]
domwoe has joined #bitcoin-wizards
Guest12765 has joined #bitcoin-wizards
<domwoe>
Was wondering if there was already a discussion about these new provably secure PoS protocols. Couldn't find anything in the logs. @andytoshi @bsm117532
<bsm1175321>
Their assumptions are far from plausible:
<bsm1175321>
(1) the network is highly synchronous, (2) the majority of the selected stakeholders is available as needed to participate in each epoch, (3) the astakeholders do not remain offline for long periods of time
<bsm1175321>
None of those are true, and...DDoS.
nooblord has joined #bitcoin-wizards
<bsm1175321>
Bitcoin's PoW has an ex-post-facto leader, which is a huge advantage -- the only way to stop the system is to DDoS ALL miners. Traditional PAXOS-derived systems have the leader known by everyone in advance, and as such are not Byzantaine fault tolerant against adversaries that target the leader.
nikivi has quit [Quit: zzz]
<domwoe>
SnowWhite desires "robustness in a sleepy network". Isn't that -not- highly synchronous
<bsm1175321>
A distributed system is fundamentally asynchronous. Assuming synchronicity is famously one of the eight fallacies of distributed computing. The assumption in bitcoin results in orphans, and the selfish mining attack. It's a bad assumption.
jannes has quit [Ping timeout: 260 seconds]
e0_ has joined #bitcoin-wizards
e0_ has quit [Quit: leaving]
<domwoe>
ok, I see you quoted the assumptions of the first paper. The second paper, however, doesn't have the synchronicity assumption
<domwoe>
But I'm really missing a comprehensive conclusion in this paper
ThomasV has joined #bitcoin-wizards
huseby has quit [Quit: WeeChat 1.6]
MoALTz has joined #bitcoin-wizards
Firescar96 has joined #bitcoin-wizards
domwoe has quit [Remote host closed the connection]
Firescar96 has quit [Ping timeout: 250 seconds]
Aranjedeath has joined #bitcoin-wizards
domwoe has joined #bitcoin-wizards
domwoe has quit [Ping timeout: 256 seconds]
Firescar96 has joined #bitcoin-wizards
BashCo has quit [Remote host closed the connection]
xissburg has quit [Quit: ZZZzzz…]
huseby has joined #bitcoin-wizards
Firescar96 has quit [Ping timeout: 260 seconds]
xissburg has joined #bitcoin-wizards
DigiByteDev has quit [Quit: DigiByteDev]
chjj has quit [Ping timeout: 250 seconds]
domwoe has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
kkode has quit [Ping timeout: 265 seconds]
vghzfkgh has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
WungFu has joined #bitcoin-wizards
vghzfkgh has quit [Remote host closed the connection]
WungFu has quit [Ping timeout: 260 seconds]
instagibbs_ has joined #bitcoin-wizards
<instagibbs_>
roasbeef: you said you had no-trusted-dealer ecdsa treshold sig paper for me couple weeks back?
<instagibbs_>
"Paillier encryption" yeah this is the one thanks
<kanzure>
(including the table in the last link)
<instagibbs_>
roasbeef: "Secondly, this means that t ≤ (n + 1) / 2. This scheme will thus be unable to realize a 2-out-of-2 signature. In the Bitcoin context, this means that two-factor security cannot be implemented with this scheme. (The error in the first draft of our paper arose because we didn’t realize that t’ > t in the Gennaro et al. scheme.)" Ok that's where my memory was coming from
<roasbeef>
in the paper they use the scheme to construct a ZKCP, but can be on independant use outside of that particular use-case
<roasbeef>
as interaction from both parties is required to generate the signature, neither side can re-sign unilaterally
CrazyLoaf has joined #bitcoin-wizards
<roasbeef>
also only one side gets a sig at the end of the protocol
ThomasV has quit [Ping timeout: 252 seconds]
<instagibbs_>
roasbeef: yes it's mentioned in the blog post
<instagibbs_>
thanks
WungFu has joined #bitcoin-wizards
harrymm has quit [Ping timeout: 252 seconds]
Guyver2 has joined #bitcoin-wizards
Guest12765 has quit []
harrymm has joined #bitcoin-wizards
Cory has joined #bitcoin-wizards
Cory has quit [Excess Flood]
Cory has joined #bitcoin-wizards
Cory has quit [Excess Flood]
ThomasV has joined #bitcoin-wizards
Cory has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 244 seconds]
<AaronvanW>
in gmaxwell his CoinSwap proposal on bitcointalk, it says: "CoinSwap results in the participants knowing the linkage."
<AaronvanW>
is that because of the HTLCs?
nikivi has quit [Quit: irc]
<instagibbs_>
AaronvanW: I assume that just means if I swap with you, we both know we swapped.
nikivi has joined #bitcoin-wizards
<AaronvanW>
instagibbs_: yeah but isn't the point that there is no linkage? that is the very first sentence of the proposal: "Alice would like to pay Bob, but doesn't want the whole world (or even Bob) tracing her transactions."
<AaronvanW>
am I misunderstanding something?
nikivi has quit [Client Quit]
<instagibbs_>
They key here is "participants"
<instagibbs_>
non-participants can only do time-correlation or whatever, but no direct on-chain linkage.
<AaronvanW>
instagibbs_: right, that's what I figured. The "(or even Bob)" part of the intro-sentence through me off though...
blackwraith has joined #bitcoin-wizards
priidu has quit [Ping timeout: 265 seconds]
roconnor has quit [Ping timeout: 252 seconds]
GreekMiner2 has joined #bitcoin-wizards
GreekMiner has quit [Ping timeout: 265 seconds]
e4xit has joined #bitcoin-wizards
davec has quit [Read error: Connection reset by peer]
davec has joined #bitcoin-wizards
nikivi has joined #bitcoin-wizards
<adiabat>
coinshuffle with > 2 participants can help with that; even participants of the coinjoin don't know the linkage
nikivi has quit [Quit: irc]
xissburg has quit [Quit: ZZZzzz…]
c0rw1n has joined #bitcoin-wizards
Topogetcyrpto has quit [Quit: Topogetcyrpto]
Davasny has joined #bitcoin-wizards
<musalbas>
kanzure, yes so my hypothesis is that if you have a merkle tree structure that has O(log(n)) non-inclusion proofs as well as O(log(n)) or better proofs of consistency, you can shift double-spend detection to the client-side (not probabilistic; with 100% accuracy) without requiring full nodes to check double-spends, and from there you can build a cryptocurrency that scales with the number of nodes in the network
<kanzure>
so to make a payment you would give the recipient a huge list of non-inclusion proofs for all the intermediate states where you want to show that no spends happened?
<bsm117532>
I think the fly in the ointment there is the consistency proof...
<musalbas>
kanzure, yes, which obviously the issue is that the proofs will grow in MB over time as has been discussed previously, but I think there could be a way to distribute that across the nodes
<musalbas>
bsm117532, you think that efficient consistency proofs aren't possible?
<kanzure>
other client-side validation proposals limit the client-side proofs to merely the ones to prove inclusion at certain points in history or something
<bsm117532>
I don't think they're impossible, but I don't know an efficient way, without having all the data.
<kanzure>
(which laso end up becoming multiple megabytes. but non-inclusion proofs over the intermediate states? that's surely even more data, unless i'm misunderstanding.)
<kanzure>
*also
<musalbas>
bsm117532, well petertodd above claims his Merbinner trees can do that, but are they O(log(n)) or O(n)? if latter, it's not efficient. <musalbas> petertodd, so using the Merbinner tree stuff you linked me to, does it support efficient consistency proofs between a tree and its updated version? i.e. like MMR/CT merkle trees. it seems like it looking at https://github.com/petertodd/python-merbinnertree/blob/master/merbinnertree/__init__.py
<musalbas>
#L469 <petertodd> musalbas: yes, the underlying data structure certainely can do that, and IIRC it's implemented too
<musalbas>
kanzure, but as I understand correctly, the other client-side proposals require miners to check for double-spends or no?
<kanzure>
well the others have probablistic fraud or whatever, which originates from i forget
<kanzure>
even if miners aren't themselves checking for double spends in those other proposals
<musalbas>
if they require to check for double-spends then mining is done at O(n) efficiency. I want to achieve O(log(n)) efficiency
<kanzure>
(except for their fees they receive/take)
<kanzure>
i'd have to ask petertodd to figure out which aspects requird probabilistic validation and why it wasn't full validation
<kanzure>
anyway, i agree with your goal of non-probabilistic validation :P
<bsm117532>
musalbas: Correct me if I'm wrong, but every transaction results in a new root hash, no? So there's no sense that you can "divide up" the work among many nodes -- all nodes need to see all transactions in order to compute the new root hashes.
<musalbas>
bsm117532, so there's something that I think most people haven't thought of when thinking about this, I've written it somewhere, one second..
<musalbas>
"since appending items to a MMR is deterministic, then a wallet - and a cold wallet - does not necessarily need to moniter the network to spend coins in the future, as long as there are nodes that store all merkle consistency proofs for blocks exist - which would be a requirement to be able to bootstrap full nodes
<musalbas>
because if a client knows that the merkle proof for a utxo at block n, such a node would be also able to determine the merkle proof for the same utxo at block n + k, by calculating the new location of the child of the proof by inferring the difference between the number of txos between those two blocks by looking at the merkle consistency proofs between those two blocks."
xissburg has joined #bitcoin-wizards
<musalbas>
so the fact that there is a new root hash, does not mean that merkle-proofs for old hashes are useless
<musalbas>
because the new merkle-proof can easily be inferred by any full node
<musalbas>
by some simple math
<bsm117532>
Hmmm...
<bsm117532>
Full nodes still need to keep the entire tree though, so the work is not divided up
<bsm117532>
I'm looking for a solution where a node has a fraction of the tree, yet the tree kept consistent collaboratively.
<musalbas>
bsm117532, they don't need to see all transactions in order to compute the new root hashes, that's point of merkle trees...
<musalbas>
bsm117532, the same way you can compute a new bitcoin block just based on the previous block, without seeing all the blocks before it
<bsm117532>
Ok I don't understand how that works then.
<musalbas>
<bsm117532> I'm looking for a solution where a node has a fraction of the tree, yet the tree kept consistent collaboratively.
<musalbas>
that's possible. merkle consistency proofs for MMRs can be done without seeing all the childs
<musalbas>
and it's referring to a MMR-like structure
<musalbas>
in an MMR, you can add a million items to the tree, and the consistency proof will still be extremely small
<musalbas>
that's the beauty of it
blackwraith has quit [Ping timeout: 252 seconds]
<arubi>
musalbas, sorry, can you explain "you can compute a new bitcoin block just based on the previous block, without seeing all the blocks before it", I understand that, but if the history isn't validated, then the root might be invalid, no?
<kanzure>
yes you still need to stay online and collect the consistency proofs (or recalculate your proofs in your wallet) because otherwise there is little reason for others to store the intermediate updates for you, or something
<bsm117532>
How does this not result in a "tree" with one long branch?
<kanzure>
arubi: clients are responsible for validating the proofs that they receive from payers
<bsm117532>
(e.g. the right subtree contains one element, over and over again)
<musalbas>
arubi, yep, but I'm proposing a system there is no such thing as an "invalid" history, except if someone broke the append-only rules of the chain. i.e. all data in blocks is valid and validation is done by the clients, not full nodes
<arubi>
thank you both, I see I'll need to read the back log a bit
<kanzure>
bsm117532: so, i don't know if there's a better answer to your question, but one possible answer is that miners should be incentivized to take fees only in situations where the fee proofs are not infinitely huge and therefore unspendable. they wouldn't mine those blocks, i think. or they would prefer to mine blocks that don't extremely bloat that situation.
<musalbas>
kanzure, you don't need to collect anything, or stay online. if you have a txout merkle-proof from 1000 blocks ago and give it to an up-to-date node to spend it, they can spend it without you giving them any more information
<musalbas>
<bsm117532> How does this not result in a "tree" with one long branch?
<musalbas>
are you talking about the actual tree in the blockchain, or the transaction proofs
<musalbas>
bsm117532, the point of MMRs is to have perfect binary trees, so trees with one long branch are avoided
<bsm117532>
I'm just looking at the diagram in the RFC, imagining adding one hash at a time. Each new hash becomes a new right subtree, with the previous tree becoming the left subtree.
<musalbas>
(but does not contain an explanation of the consistency proofs)
<bsm117532>
I've read all this before, but now forgotten it... :-/
<musalbas>
bsm117532, so the point in MMRs is that the tree is "rebalanced" on the fly
<musalbas>
to make a perfect binary tree
<musalbas>
or as close to one as possible
<kanzure>
perhaps i was thinking of similar proposals that also incorporated pruning. hrm.
<kanzure>
or because of this: "because the new merkle-proof can easily be inferred by any full node"
<musalbas>
i'm not great at explaining things
<bsm117532>
Isn't the rebalancing extremely expensive? That's the usual argument for why this kind of data structure isn't being used for UTXO set commitments...
<musalbas>
bsm117532, no that's the beauty of MMR/RFC6962-like trees. Rebalancing is insanely efficient
<musalbas>
i mean i'm not even sure i'd call it rebalancing
<bsm117532>
So imagine I have a UTXO set commitment, and I want to modifyit by the new UTXO's in a block...
<bsm117532>
If it's so efficient, why are we not doing this in bitcoin again?
<musalbas>
bsm117532, not too sure about that one
<musalbas>
the rebalancing is only efficient when it's append-only
<musalbas>
i haven't read too much on the utxo set commitment proposals for bitcoin
<bsm117532>
Well, a spent transaction output set is append only...
<musalbas>
(and maybe i'm using the term 'rebalancing' wrong, in this context I'm using it to mean to have a perfect binary tree)
<musalbas>
(though this will take me a while to understand :P)
WungFu has quit [Ping timeout: 260 seconds]
xissburg has quit [Quit: ZZZzzz…]
<kanzure>
actually that is a good thing to link you to. good log.
<kanzure>
looks like for some reason i was insisting on validation work in addition to the deltas
xissburg has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
chjj has joined #bitcoin-wizards
domwoe has quit [Remote host closed the connection]
nikivi has joined #bitcoin-wizards
Topogetcyrpto has joined #bitcoin-wizards
MoALTz has quit [Quit: Leaving]
nikivi has quit [Quit: irc]
aalex has quit [Ping timeout: 250 seconds]
Guyver2 has quit [Quit: :)]
aalex has joined #bitcoin-wizards
chjj has quit [Ping timeout: 244 seconds]
aalex has quit [Max SendQ exceeded]
aalex has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
e4xit has quit [Quit: e4xit]
Davasny has quit [Read error: Connection reset by peer]
e4xit has joined #bitcoin-wizards
pro has quit [Ping timeout: 252 seconds]
pro has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
igno_peverell has joined #bitcoin-wizards
<igno_peverell>
I have a minimal implementation of MimbleWimble available. It's very far from complete but has the basics, included the summing of pedersen commitments: