10:42 UTC

< October 2016 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

- Console
- #amber
- #apicula
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #buildbot
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #lowempire
- #maemo-leste
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- ##moved_to_libera
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #openwrt-devel
- #panfrost
- ##panfrost-offtopic
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #river
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #stellar
- #stellar-dev
- ##stm32-rs
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #videocore
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

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

<petertodd>
musalbas: yes, the underlying data structure certainely can do that, and IIRC it's implemented too

<adiabat>
nsh: nope, still 2 chains. I can only get one working, the other I observe only from block explorer websites

<adiabat>
http://tbtc.blockr.io/ https://www.blocktrail.com/tBTC https://test.webbtc.com/ are currenly on a 1M 9K chain

<adiabat>
https://live.blockcypher.com/btc-testnet/ https://testnet.smartbit.com.au/ are currently on the 1M 8K chain

<adiabat>
last block in common looks like 0000000000e0f4516a7558eb92a0d4cbfd630c6bce18c181b8515ebee5fa399a

<adiabat>
after which the branch I get with 0.13.0 goes to 0000000000af7aac1817b82d377fa989407d607dc1953d63827d8adfa39de85b

<adiabat>
and some of the block explorers go to 00000000008818f4b21dc6203b9c86f2c8b2aa694c0d46106a5e2baf93dcc691

<musalbas>
petertodd, :o that has very useful applications then (if the consistency proofs can be done in O(log(n)) or less time like MMRs

<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.

<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>
(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>
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.

<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.

<domwoe>
ok, I see you quoted the assumptions of the first paper. The second paper, however, doesn't have the synchronicity assumption

<instagibbs_>
roasbeef: you said you had no-trusted-dealer ecdsa treshold sig paper for me couple weeks back?

<kanzure>
http://diyhpl.us/~bryan/papers2/bitcoin/Securing%20Bitcoin%20wallets%20via%20a%20new%20DSA%20ECDSA%20threshold%20signature%20scheme.pdf

<kanzure>
http://diyhpl.us/~bryan/papers2/bitcoin/Securing%20Bitcoin%20wallets%20via%20threshold%20signatures.pdf

<instagibbs_>
"The desktop acts as a trusted dealer when distributing the phone’s keyshare" <--- without that

<kanzure>
and https://freedom-to-tinker.com/2014/05/23/threshold-signatures-and-bitcoin-wallet-security-a-menu-of-options/

<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>
keygen is on page 11 of this, and signing is on page 14: https://eprint.iacr.org/2016/451.pdf

<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

<AaronvanW>
in gmaxwell his CoinSwap proposal on bitcointalk, it says: "CoinSwap results in the participants knowing the linkage."

<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."

<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...

<adiabat>
coinshuffle with > 2 participants can help with that; even participants of the coinjoin don't know the linkage

<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?

<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

<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.)

<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?

<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>
i'd have to ask petertodd to figure out which aspects requird probabilistic validation and why it wasn't full validation

<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."

<musalbas>
so the fact that there is a new root hash, does not mean that merkle-proofs for old hashes are useless

<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

<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>
in an MMR, you can add a million items to the tree, and the consistency proof will still be extremely small

<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

<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

<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, 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>
bsm117532, the structure is better explained here https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md

<kanzure>
or because of this: "because the new merkle-proof can easily be inferred by any full node"

<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

<bsm117532>
So imagine I have a UTXO set commitment, and I want to modifyit by the new UTXO's in a block...

<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>
bsm117532, I recalling there being some proposals for Bitcoin to have UTXO sets using MMRs to have better scalability

<yoleaux>
musalbas: Sorry, I don't know what timezone that is. If in doubt, see https://en.wikipedia.org/wiki/List_of_tz_database_time_zones for a list of options.

<kanzure>
also i have been trying to convince musalbas to read the conversation between petertodd and bramc https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/012764.html

<musalbas>
however discussion about hardware-efficient merkle trees isn't the interesting part i think

<bsm117532>
Haven't heard from bramc for a long time, but I talked a lot with him about optimizing his Merkle tree implementation...

<kanzure>
i think the search term is deltas and delta commitments http://gnusha.org/bitcoin-wizards/2015-09-18.log