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
PERSIAN has quit [Ping timeout: 260 seconds]
<fluffypony>
kanzure: you need traceability to prevent double spends (in a cryptocurrency setting) and double votes (in a blind voting setting)
belcher has quit [Ping timeout: 265 seconds]
<kanzure>
fluffypony: i need something other than an accumulator. i need to check if a pubkey participated in a signature, without having a list of all the pubkeys that made the group signature (or aggregate signature or something).
<fluffypony>
hmmmm
<fluffypony>
yeah in Monero's ring sigs you can see all the pubkeys, and whilst the key image doesn't reveal the true signer it does require the pubkeys to verify
<fluffypony>
I don't know if you can have verification of the traceable component without revealing the pubkeys in a ring
<fluffypony>
and not being able to verify the trace is obviously bad, because then it could be false
<kanzure>
also i would like this magic to be constant size
<fluffypony>
bed time, I'll give this some thought tomorrow
<kanzure>
thank you
belcher has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
CubicEarth has quit []
Ylbam has quit [Quit: Connection closed for inactivity]
Dizzle has joined #bitcoin-wizards
Dizzle__ has quit [Ping timeout: 245 seconds]
PaulCapestany has joined #bitcoin-wizards
<kanzure>
it's interesting to think about history size limits and rate limits in a client-side validation scheme perspective-- it can be a rate limit on transaction history size growth, or on total number of transactions, many other things.
Dizzle has quit [Quit: Leaving...]
Topogetcyrpto has quit [Quit: Topogetcyrpto]
<kanzure>
Taek: have you described your "no blocks, only transactions" scheme somewhere?
CrazyLoaf has quit [Quit: Connection closed for inactivity]
airbreather has quit [Remote host closed the connection]
airbreather has joined #bitcoin-wizards
Topogetcyrpto has joined #bitcoin-wizards
kankles has quit [Ping timeout: 250 seconds]
kankles has joined #bitcoin-wizards
Topogetcyrpto has quit [Quit: Topogetcyrpto]
dgenr8 has joined #bitcoin-wizards
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
rusty2 is now known as rusty
rusty has quit [Quit: Leaving.]
rusty2 has joined #bitcoin-wizards
CrazyLoaf has joined #bitcoin-wizards
Topogetcyrpto has joined #bitcoin-wizards
Burrito has quit [Quit: Leaving]
alpalp has quit [Ping timeout: 264 seconds]
pro has quit [Quit: Leaving]
rusty2 has quit [Ping timeout: 250 seconds]
ThomasV has joined #bitcoin-wizards
Transisto2 has joined #bitcoin-wizards
Madars has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 260 seconds]
<Taek>
kanzure: It evolved in to Jute, which is the presentation I gave in Milan
wasi has quit [Ping timeout: 245 seconds]
<kanzure>
alright. i've been looking at a way to do a scheme with a single merkle root of a merkle tree of arbitrary data. starting to look into all the DAGy parts i might want to put in there.
<Taek>
I think client side validation has a lot of potential, but you still need some guarantee of extensibility
<Taek>
err - my understanding of client side validation is that you now somekthing is valid becuase the spender gives you the whole history of the transaction, which makes it easy for you to know that the transaction is correct without having the whole history of everythign
<kanzure>
Taek: my problem at the moment is that blocks require a list of pubkeys, and i'm trying to eliminate that requirement :\ otherwise it's O(n) block size again
<Taek>
are we talking about Peter Todd's work?
legogris has quit [Remote host closed the connection]
<Taek>
my understanding is that you only need to download the history relevant to you
<Taek>
which would include the public key stuff
legogris has joined #bitcoin-wizards
<kanzure>
Taek: so, in my shceme, blocks do not include merkle tree updates/deltas/diffs
<Taek>
pardon if I missed a link from earlier, but do you have a general description somewhere?
<kanzure>
start near "weirdo proof-of-publication scheme"
<kanzure>
also i can eliminate the list of output hashes in that description, in exchange for an extra client-side consensus rule (which is a good trade in my opinion)
Alopex has quit [Remote host closed the connection]
wasi has joined #bitcoin-wizards
TheSeven has quit [Ping timeout: 245 seconds]
TheSeven has joined #bitcoin-wizards
<kanzure>
and now the trick is to eliminate the list of pubkeys. somehow. :|
Alopex has joined #bitcoin-wizards
<Taek>
hmm
<Taek>
how do you get rid of the output hashes?
<kanzure>
Taek: use same merkle tree location determined by pubkey or some other previous detail from history. always use same location.
<kanzure>
list of output hashes was to prevent double spending. but having only one possible location for a double spend to appear at eliminates this problem (for a double spend in the current block).
<Taek>
That's more or less what I was picturing
<Taek>
but, you need to see the data in that merkle tree location every block to know that the output wasn't spent
<kanzure>
no :)
<Taek>
oh?
<kanzure>
say you're a recipient receiving a bunch of merkle inclusion proofs
<Taek>
oh is that what the list of public keys is for?
<kanzure>
the spender says yo dawg i don't have a proof for block N
<kanzure>
in the normal scheme you would say "well in block N you probably are hiding a double spend, so... give me the merkle inclusion proof"
<kanzure>
for a spender that was offline during block N, he wont have any merkle inclusion proof to share you, right? this is indistinguishable from the malicious behavior :D.
<kanzure>
so the alternative is to have the list of pubkeys yes
<kanzure>
now, a list of pubkeys can be forged by a miner, therefore you need an aggregate signature where all the participants sign the merkle root (as an indication that yes they received a merkle inclusion proof from the miner)
<kanzure>
so a potential recipient needs to be able to check all the intermediate blocks (between merkle inclusion proofs for each 'coin') to determine whether the recipient should expect to receive a merkle inclusion proof
<kanzure>
if they do not receive the proof, then the recipient knows that they might be receiving double spent coins
<kanzure>
so eliminating the list of pubkeys-- but keeping that property--- is important because you get a <10 kb block size for almost arbitrarily many transactions.
<Taek>
I see
<Taek>
it's interactive then
<Taek>
at least as I currently understand it
<Taek>
where, first you have the 'aggregating' phase, where everyone is submitting transactions to the miner, and then you have the inclusion signing phase
<Taek>
hmm
<Taek>
maybe there is some wiggle room to cut down on interactivity
<kanzure>
sure, there's some problems there, and also the merkle inclusion proof stuff is a huge huge burden on clients
<Taek>
depends I guess on how complex the history of the transaction is
<kanzure>
it would probably grow pretty huge. but perhaps there's various kinds of magic to deal with that elsewhere.
<kanzure>
and also, the interactivity puts a constraint on history growth at least inside a single block, because of DoS problems as you grow the size of the number of spenders heh
<kanzure>
(although the DoS problems might not be real--- if someone doesn't sign, that might be OK. it's just invalid data.)
<Taek>
well, you've got this ability to compress things a lot, maybe enough that you can put strict spendability rules on an output. For example, it can only be spent to a single input
<Taek>
this means that the history of the output grows linearly with the number of times it has been spent, as opposed to exponentially
<Taek>
it also means that people with more money have more history, because you'd probably set every output to like 0.0001 btc or something
<Taek>
and that seems pretty fair to me
<kanzure>
my number one priority was looking at the block data structure, before thinking about transaction history proof size reduction stuff
<Taek>
yeah still stuck with those public keys
<kanzure>
and O(n) list of pubkeys is a real bummer
<Taek>
well, this seems like something that snarks might be useful for
<Taek>
the O(n) pubkeys + sigs being the input, and a snark sig being the output
<Taek>
though that's still not good enough imo because the interactivity requirements are pretty big
windsok has quit [Ping timeout: 250 seconds]
<kanzure>
the output is just a signature over the merkle root, for each pubkey or something, to prove that the spenders have received their merkle inclusion proofs
<Taek>
right
<kanzure>
well, so, the other way to think about this is: design a system where you know that the entire block data structure is just a merkle root and some other constant size data. and then build up from there.
<kanzure>
if you were okay with long-hiding double spends, you could just use a merkle root and be done with it
<kanzure>
clients would be responsible for detecting double spends in transaction graph history data
<kanzure>
however, literally anyone could collude with any miner to introduce a double spend
<Taek>
right
wasi has quit [Ping timeout: 245 seconds]
<Taek>
having a giant list of public keys is still better I think than what we're doing today
<Taek>
it's like maybe 4x scalability or something, in terms of what data is necessary for everyone to store
<kanzure>
well if each pubkey is 32 bytes, do the math, it's like 30k transactions/block only
<kanzure>
where are you getting 4x from btw?
<Taek>
mostly pulled it out of the air. Transactions are 225 bytes today, and with this you can squeeze it down to 32 + some constant factor
<Taek>
but you lose a lot of the scriptability
CrazyLoaf has quit [Quit: Connection closed for inactivity]
<kanzure>
the scriptability is on the client side, it's still there
<Taek>
oh right
<kanzure>
.wa 1 MB / 32 bytes
<yoleaux>
kanzure: Sorry, no result!
<Taek>
31,250
<Taek>
:p
<Taek>
I guess then that everything else is constant size
<kanzure>
it feels very strange that a merkle root scheme like this is limited to only 31,250
<Taek>
So, if we combine a scheme like this with something like Jute and push the block size out to say... 10 MB, that's 15 billion transactions per year. Which is enough to scale to the whole planet if most everyone is using lightning
<kanzure>
somehow i thought a merkle tree scheme should get us way more than 31,250/block
wasi has joined #bitcoin-wizards
<kanzure>
Taek: it might be more than 31,250/block technically... since the same pubkey could refer to multiple inputs.
<Taek>
so we need a way to eliminate the public keys, and ideally also a way to remove the interactivity from the inclusion proof
<kanzure>
to eliminate the interactivity, you would have to include the inclusion proofs in the block data. tada! but this is going in the opposite direction :).
<Taek>
also, have to be careful about how much burden is being placed on the miner - providing 30,000 inclusion proofs to people making requests is going to be a bottleneck at some ponit
<Taek>
though it's a lot easier than having blocks of the same size, because instead of doing the data through a flood network it's all direct-to-spender
<kanzure>
no, the miner can choose to make a small block
<Taek>
and collect less fees, which would be a centralization pressure
<kanzure>
if they can't handle 30,000 inclusion proofs then they can just do a handful of inclusion proofs --- in fact, some spenders could do aggregation, and then distribute inclusion proofs to their multisig participants etc
<Taek>
aggregation might also be how you eliminate smoe of the interactivity
<Taek>
If I recall, some of the MAST signature stuff has a way to deal with absent participants
<Taek>
basically the size of the signature grows with the number of people absent from the signing process
<kanzure>
re: collecting less fees, i dunno if that's true.... so, the bottleneck is actually miner's validation of historical data. it's not the ability to generate inclusion proofs. if you encourage everyone to submit through multisig, then you only give back 1 inclusion proof. it's the validation of prior history that kills a small miner.
<Taek>
doesn't need to be the miner's job to only include valid transactions
<kanzure>
if you had lots of "freshly minted" fees, a small miner can take that almost immediately, without any difficulty, for almost an arbitrary number of transactions
<Taek>
miner shouldn't have to do any script verification
<kanzure>
miners must do script verification --- how do they check their fees? :D
<Taek>
ah darn
<kanzure>
but yes, other than fees, miners can include totally invalid wacky stuff, sure
<kanzure>
which they are welcome to do.
<kanzure>
in fact, if you're a small miner, perhaps you outsource your history validation or you accept any history of any fee at all, on the hopes that you can later upgrade to beefier hardware. but you could also instead choose to accept coins with shorter histories... if a coin was mined 500 blocks ago, spent once, you only have 2 inclusion proofs or something, it's not so bad... it's only coins ...
<kanzure>
...that have a lot of weird history that become problematic for small miners.
<Taek>
hmm I really like the way you can skip the inclusion proofs by mandating that inclusion proofs are only valid if there's a signature from the spender in the block header
<kanzure>
and likewise: coin spends are only valid if the signature is in the block too
<kanzure>
(well, a related signature at least)
<Taek>
you could also make life easier for the miner by paying the fee using outputs with little history
<kanzure>
also.... if you're transacting a lot, you're incentivized to go do that on some other system. only use on-chain for occasional movements.
<kanzure>
(because doing many transactions increases the history size)
<kanzure>
yes, in general you would select coins that have little history, not just for the miner fee but for all of your spends
<Taek>
it is interesting because it means coins with more history are worth less
<kanzure>
the client-side can also have some pruning rules if you were really worried about transaction history hyper growth.... after a transaction has been in the strong set for a certain amount of time, perhaps it's okay to assume it doesn't need further validation. (not to mention that everyone is already doing validation caching of course)
Giszmo has quit [Quit: Leaving.]
<kanzure>
Taek: what kind of DAG goodness can be applied to this?
<Taek>
The dag stuff that I've been working on is mostly concerned with turning a dag into a line
<kanzure>
and weak blocks in parents
<Taek>
Or rather, taking a bunch of blocks that were produced in parallel and finding a secure way to get a strict/total ordering on them
<Taek>
so, I don't think most of that applies here
<kanzure>
in my scheme, you can give very tiny output amounts to small cpu miners i think
<Taek>
?
<Taek>
I don't quite follow
windsok has joined #bitcoin-wizards
<kanzure>
the client-side rules can be whatever; the miner splits the coinbase output into a hundred billion pieces or something.
<Taek>
ah
<Taek>
hmm
<Taek>
that's almost more p2pool-ish
<Taek>
I'll have to sleep on it some, this seems like a pretty interesting way to build up a block
<Taek>
re: the script stuff, you'd really end up with like 2 scripts
<Taek>
the first is the one that is public and seen by everyone, and the second is the one that's only seen by the validator
<Taek>
because, if you're doing something like m-of-n multisig, you need any 'm' to be able to spend the output
<Taek>
but if you only have 1 public key, you essentially get a situation where any of the 'n' can spend the output and then withhold the data from everyone else
<Taek>
they might spend the output in an invalid way, but nobody would ever know because the data is being withheld
Transisto2 has quit []
<kanzure>
err i think maybe coalitions in a multisig scheme would be able to double spend each other, based on which coalition signed last time or something? i dunno
<Taek>
they couldn't double spend I don't think, just prevent the other person from spending
Chris_Stewart_5 has quit [Ping timeout: 250 seconds]
Ylbam has joined #bitcoin-wizards
xissburg has quit [Quit: ZZZzzz…]
Chris_Stewart_5 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 252 seconds]
ThomasV has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy has quit [Ping timeout: 258 seconds]
ThomasV has quit [Ping timeout: 264 seconds]
BashCo has quit [Remote host closed the connection]
BashCo has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 250 seconds]
CubicEarth has joined #bitcoin-wizards
BashCo has joined #bitcoin-wizards
CubicEarth has quit [Read error: Connection reset by peer]
ThomasV has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has quit [Changing host]
Emcy_ has quit [Ping timeout: 268 seconds]
Transisto2 has joined #bitcoin-wizards
windsok has quit [Ping timeout: 245 seconds]
CubicEarth has quit [Read error: Connection reset by peer]
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy has quit [Ping timeout: 268 seconds]
Ylbam has quit [Quit: Connection closed for inactivity]
rusty2 has joined #bitcoin-wizards
windsok has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has quit [Changing host]
xissburg has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 258 seconds]
ManfredMacx has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 252 seconds]
droark has quit [Ping timeout: 268 seconds]
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy has quit [Ping timeout: 258 seconds]
CubicEarth has joined #bitcoin-wizards
shesek has quit [Ping timeout: 260 seconds]
Emcy has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has quit [Changing host]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
Emcy_ has quit [Ping timeout: 260 seconds]
rusty2 has quit [Ping timeout: 246 seconds]
shesek has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
paveljanik has quit [Ping timeout: 248 seconds]
Emcy has quit [Ping timeout: 246 seconds]
warren has quit [Ping timeout: 265 seconds]
adam3us has quit [Ping timeout: 260 seconds]
Emcy has joined #bitcoin-wizards
warren has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 248 seconds]
adam3us has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
AaronvanW has quit [Remote host closed the connection]
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Topogetcyrpto has quit [Ping timeout: 248 seconds]
Topogetcyrpto has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 264 seconds]
ThomasV has joined #bitcoin-wizards
Emcy_ has quit [Read error: Connection reset by peer]
Emcy has joined #bitcoin-wizards
Topogetcyrpto has quit [Ping timeout: 258 seconds]
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy has quit [Ping timeout: 258 seconds]
ThomasV has quit [Ping timeout: 252 seconds]
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 258 seconds]
CrazyLoaf has joined #bitcoin-wizards
Topogetcyrpto has joined #bitcoin-wizards
paveljanik has joined #bitcoin-wizards
paveljanik has quit [Client Quit]
CubicEarth has quit [Remote host closed the connection]
CubicEarth has joined #bitcoin-wizards
Lambda_ has quit [Read error: Connection reset by peer]
BashCo has quit [Read error: Connection reset by peer]
CubicEarth has quit [Ping timeout: 268 seconds]
Topogetcyrpto has quit [Ping timeout: 265 seconds]
BashCo has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
AaronvanW has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Changing host]
kankles has quit [Quit: Leaving]
Emcy has quit [Ping timeout: 256 seconds]
ManfredMacx has quit [Quit: Bye]
ManfredMacx has joined #bitcoin-wizards
BashCo_ has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 264 seconds]
ThomasV has quit [Ping timeout: 258 seconds]
kumavis has quit []
kumavis has joined #bitcoin-wizards
runeks has quit []
runeks has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
Muis has quit []
Muis has joined #bitcoin-wizards
tromp_ has quit [Read error: Connection reset by peer]
CubicEarth has joined #bitcoin-wizards
bassguitarman has quit []
bassguitarman has joined #bitcoin-wizards
CubicEarth has quit [Remote host closed the connection]
wpalczynski has quit []
wpalczynski has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
SirJacket has quit []
SirJacket has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 260 seconds]
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
laurentmt has joined #bitcoin-wizards
catcow has quit []
catcow has joined #bitcoin-wizards
laurentmt has quit [Read error: Connection reset by peer]
Emcy has quit [Ping timeout: 265 seconds]
Emcy has joined #bitcoin-wizards
Emcy has quit [Changing host]
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 265 seconds]
adams__ has quit []
adams__ has joined #bitcoin-wizards
da2ce7 has quit [Ping timeout: 260 seconds]
poggy has quit [Ping timeout: 260 seconds]
_mn3monic has quit [Ping timeout: 260 seconds]
Hunger- has quit [Ping timeout: 260 seconds]
Tenhi has quit [Ping timeout: 268 seconds]
da2ce7 has joined #bitcoin-wizards
Hunger- has joined #bitcoin-wizards
poggy has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
echonaut has quit [Read error: Connection reset by peer]
laurentmt has quit [Client Quit]
echonaut10 has joined #bitcoin-wizards
Tenhi has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Emcy has quit [Ping timeout: 268 seconds]
JackH_ has joined #bitcoin-wizards
harrymm has quit [Remote host closed the connection]
JackH has quit [Ping timeout: 258 seconds]
tromp_ has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
arubi has quit [Remote host closed the connection]
arubi has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has quit [Changing host]
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 260 seconds]
harrymm has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
ManfredMacx has quit [Quit: Bye]
CubicEarth has quit []
<Taek>
I thought of a way to make the interactivity requirements not as rough. Basically you let the miner include a bunch of Merkle roots instead of just one Merkle root, and then you leave it to the participants to collaborate to build the Merkle root + key set + inclusion proofs
<Taek>
That way the miner doesn't need to be involved in the process at all
nicolagreco has quit []
CrazyLoaf has quit [Quit: Connection closed for inactivity]
nicolagreco has joined #bitcoin-wizards
<kanzure>
and then there's some minor ordering problems and double spend problems, i think, but they are defeatable
<bsm117532>
kanzure: "i need to check if a pubkey participated in a signature, without having a list of all the pubkeys that made the group signature (or aggregate signature or something)."
<bsm117532>
kanzure: I think one can make an information theoretic proof that this is impossible, based on representing n bits of random data in fewer than n bits.
<bsm117532>
What you can do is use a MMR/Merklix type tree structure and present a proof of presence or absence of any one pubkey, with a log(n) sized proof.
<kanzure>
and include the pubkey inclusion proof in the block data...?
<bsm117532>
"you get a <10 kb block size for almost arbitrarily many transactions." -- there's no magic that allows compressing an infinite amount of information into a finite number of bits.
<kanzure>
you're not compressing information
<Taek>
you actually are compressing information, that's essentially what a hash function does
<Taek>
bsm117532: it's not information theoretically impossible for a few reasons
<Taek>
First, it's probabilistic. We use 32 bytes because the chance of collision is really low. So technically there are an infinite number of collisions out there, but it'd be really freaking impressive if you found one
<Taek>
That's what gets you a lot of the wiggle room
<Taek>
And then second, you encode the rest of the information off-chain
<kanzure>
for pubkeys?
<bsm117532>
So there's an OWAS type aggregation happening somewhere?
<Taek>
the question "did public key X sign blob Y" is much easier to answer in a compressed form than "tell me which public keys signed blob Y"
<Taek>
I was talking about hashes
<kanzure>
might not be OWAS ..... roasbeef/andytoshi suggested an accumulator.
<Taek>
I don't know if there's an equivalent for pubkeys, but I am arguing that it's not impossible
bassguitarman has quit [Quit: Connection closed for inactivity]
<bsm117532>
It sounds like kanzure wants to test set membership for any of the N pubkeys. While I can present a proof in O(log(N)) with a tree or O(1) with a ZKP, I can't test set membership, without additional data, at any complexity other than O(N).
<bsm117532>
(on information theoretic grounds)
Giszmo has joined #bitcoin-wizards
<Taek>
the trick is that any single participant only needs proof for a single key
<Taek>
kanzure: don't you also need a non-inclusion proof? You need the ability to look at the public key blob and say "...
<Taek>
lol nvm
<kanzure>
yes, you need noninclusion proofs
jtimon has joined #bitcoin-wizards
btcdrak has quit [Quit: Connection closed for inactivity]
Chris_Stewart_5 has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has quit [Changing host]
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 248 seconds]
ThomasV has joined #bitcoin-wizards
<bsm117532>
kanzure: That paper looks like it works probabilistically...as the set of accumulated values grows, the probability that one could create a false inclusion proof grows...
Guyver2 has joined #bitcoin-wizards
_mn3monic has joined #bitcoin-wizards
uiuc-slack has quit [Remote host closed the connection]
uiuc-slack has joined #bitcoin-wizards
btcdrak has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 250 seconds]
Topogetcyrpto has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 250 seconds]
Emcy has joined #bitcoin-wizards
Anduck has quit [Ping timeout: 246 seconds]
Anduck has joined #bitcoin-wizards
laptop__ has joined #bitcoin-wizards
JackH_ has quit [Ping timeout: 250 seconds]
binaryFate has quit [Ping timeout: 258 seconds]
binaryFate has joined #bitcoin-wizards
binaryFate has quit [Ping timeout: 258 seconds]
nikivi has joined #bitcoin-wizards
bsm117532 has quit [Ping timeout: 256 seconds]
bsm117532 has joined #bitcoin-wizards
BashCo_ has quit [Remote host closed the connection]
JackH_ has joined #bitcoin-wizards
bsm117532 has quit [Read error: Connection reset by peer]
bsm117532 has joined #bitcoin-wizards
laptop__ has quit [Ping timeout: 265 seconds]
bsm117532 has quit [Ping timeout: 258 seconds]
BashCo has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
binaryFate has joined #bitcoin-wizards
bsm117532 has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 250 seconds]
ThomasV has quit [Ping timeout: 268 seconds]
rusty2 has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
cluckj has quit [Ping timeout: 258 seconds]
cluckj has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
rusty2 has quit [Read error: Connection reset by peer]
rusty21 has joined #bitcoin-wizards
rusty21 has quit [Read error: Connection reset by peer]
rusty2 has joined #bitcoin-wizards
chjj has quit [Ping timeout: 250 seconds]
belcher has quit [Quit: Leaving]
pro has quit [Ping timeout: 250 seconds]
rusty2 has quit [Quit: Leaving.]
rusty21 has joined #bitcoin-wizards
rusty21 has quit [Ping timeout: 252 seconds]
chjj has joined #bitcoin-wizards
worstadmin_ has quit []
worstadmin_ has joined #bitcoin-wizards
worstadmin_ has quit [Client Quit]
worstadmin_ has joined #bitcoin-wizards
igno_peverell has joined #bitcoin-wizards
worstadmin_ is now known as worstadin
worstadin is now known as worstadmin
ThomasV has joined #bitcoin-wizards
wasi has quit [Remote host closed the connection]
wasi has joined #bitcoin-wizards
nikivi has quit [Quit: irc]
ThomasV has quit [Ping timeout: 258 seconds]
s0c has joined #bitcoin-wizards
s0c has quit []
paveljanik has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
paveljanik has quit [Quit: Leaving]
abpa has joined #bitcoin-wizards
se3000 has joined #bitcoin-wizards
Guyver2 has quit [Remote host closed the connection]
btcdrak has quit [Quit: Connection closed for inactivity]
brg444_ has joined #bitcoin-wizards
blackwraith has joined #bitcoin-wizards
brg444_ has quit [Client Quit]
priidu has quit [Ping timeout: 252 seconds]
brg444 has joined #bitcoin-wizards
Nightw0lf has quit [Quit: leaving]
Nightwolf has joined #bitcoin-wizards
bildramer1 has joined #bitcoin-wizards
Burrito has joined #bitcoin-wizards
bildramer has quit [Ping timeout: 260 seconds]
Newyorkadam has joined #bitcoin-wizards
se3000 has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
Newyorkadam has quit [Quit: Newyorkadam]
bildramer1 is now known as bildramer
belcher has joined #bitcoin-wizards
se3000 has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
<kanzure>
a large constant size accumulator might be okay...... just increase the time between blocks.
abpa_ has joined #bitcoin-wizards
abpa has quit [Read error: Connection reset by peer]
igno_peverell has quit [Ping timeout: 245 seconds]
Aranjedeath has joined #bitcoin-wizards
<kanzure>
15:10 <kanzure> i have a list of pubkeys and a signed message (same message signed by everyone)
<kanzure>
15:10 <kanzure> to check if pubkey N participated, you do a lookup and check the signature
<kanzure>
15:11 <kanzure> to check if they did not participate, you do a lookup and find no entry in the list
brg444 has quit [Quit: brg444]
<kanzure>
15:13 <kanzure> this is merely a way to determine if they are withholding information from you
Newyorkadam has joined #bitcoin-wizards
JackH_ has quit [Quit: Leaving]
se3000 has quit [Quit: My iMac has gone to sleep. ZZZzzz…]