log☇︎
212400+ entries in 0.136s
asciilifeform: i walked compendia of known np-hard/np-complete problems, and found that all of them had same hole
asciilifeform: http://btcbase.org/log/2016-03-20#1436710 << another thread re subj ☝︎
a111: Logged on 2016-02-10 20:10 mircea_popescu: basically showing that a+b < c is true or false for a, b, c in R is a harder-than-NP problem.
mircea_popescu: http://btcbase.org/log/2016-02-10#1402378 << i think it was thereabouts. ☝︎
mircea_popescu: where the fuck is that convo
asciilifeform: rsa doesn't pretend to a known complexity class tho.
asciilifeform: ( spoiler : can't prove the hardness of magicking ~your particular~ graph. )
mircea_popescu: yeah, it was part of that discussion.
asciilifeform: i actually worked with this notion last year, when investigating nonretarded (i.e. of provable complexity) block ciphering. and came to same realization that mircea_popescu is probably about to come to
mircea_popescu: you may be challenged to either show the hamiltonian in the homomorphic graph, or else to show the homomorphism between the graphs.
mircea_popescu: anyway. the encryption scheme is like this : you generate a large graph with a hamiltonian cycle ; and a homomorphic graph.
asciilifeform: nono we had this
mircea_popescu: what the fuck i hallucinated math discussions.
asciilifeform: can't seem to find ~this~, either
mircea_popescu: i derrided it for being impractical but i can't fucking find the discussion
mircea_popescu: and there was a scheme proposed whereby you either show the graphs or the relation ; op keeps challenging you ; each correct response increases the probabiling of truth by a factor of 2
mircea_popescu: well, deciding whether two given graphs are homomorphic is > np.
asciilifeform: ( as in, say, these : http://web.mit.edu/~ezyang/Public/graph/svg.html )
mircea_popescu: asciilifeform there's this scheme whereby i create a graph, A and a homomorphism of it A'. you get ot see A', and may challenge me
mircea_popescu: i forget wtf that is called, we discussed it.
asciilifeform: because the signing process likewise took in all of'em
mircea_popescu: (note that the decomposition needn't be Vs but will likely be a homomorphism, which POSSIBLY tyakes us straight to the hardest code known to man, the see-or-pick homomorphisms)
asciilifeform: it'd work, naturally, if the algo actually ~needed~ all of the pubkeys
mircea_popescu: tsk. not algebraically either. how the fuck would V(all) work so it's not decomposed into Vi(each)
mircea_popescu: asciilifeform re-reading i am pretty much convinced that the requirement that a) signatures are produced pairwise nevertheless b) no pairwise verification function exists yet c) verification works on a group of them is batshit insanity. might as well ask for a 5 smaller than 4.
asciilifeform: well yes, it'll eat linearly moar cycles, to verify
mircea_popescu: in FACT, the MORE sigs it uses in a ring, the more expensive the tx fee should be.
mircea_popescu: N would be small though. 2-12 ish sort of item
asciilifeform: mircea_popescu: even supposing that you had this, if you actually needed all pubkeys in use to-date to verify a sig... it'll be painful
mircea_popescu: 19yo female, bb. that's not occuring.
BingoBoingo: <omraphantom> me bored with too much time = crazy idea written out with no way to make it real << Go to lumber yard, buy wood. Go to hardware store buy tools. Make things until you start making things of complexity necessary to carry skills into building crazy things
mircea_popescu: V(K1, S1)=false, V(K2, S1)=false, .... BUT V(K1,K2,..,KN, S1) = true if and only if K1 signed S1 ; similarily with k2 and s2 all the way to n
asciilifeform: now let's say we have this primitive. how do you make, out of it, a bitcoinlike
mircea_popescu: it's worse than that, by any owner of any k in the list.
asciilifeform: as i understand, what mircea_popescu would like is : V(K1, S)=false, V(K2, S)=false, .... BUT V(K1,K2,..,KN, S) = true
BingoBoingo: <mircea_popescu> hey BingoBoingo were you in georgia ? << That's thestringpuller
asciilifeform: let's try to at least put it on paper, what would be this squared circle
mircea_popescu: once stated the pipedream portion is pretty painfully obvious ; but nevertheless, maybe ?
mircea_popescu: asciilifeform this is an "idea" item not a technological object, so bear with me. a "ring signature" is a set of signatures with a) arbitrary cardinality n which has the property that b) while it can be verified the correct signature was offered it c) can't be established wich signature that is.
asciilifeform: (or unless you want to make blocks ~very~ compact)
asciilifeform: mircea_popescu: it doesn't have to be capped at 2, either, unless you use casks and want to leave room for dozen+ hop stages
mircea_popescu: i would still love to see, for what it's work, PROPER ring signatures.
mircea_popescu: "all txn are 2 in 2 out" fixed width txn seems nailed down at this point. i can't see how an argument would work that'd offset the evident gains.
mircea_popescu: yeah. fixed width tx has some serious advantages.
asciilifeform: for folx tuned in : it also makes the cask thing possible, but the latter is wholly separate, optional algo, it is possible to use traditional mempools with this scheme
asciilifeform: mircea_popescu: fixed-width tx buys us this algo. but not only it. for instance, an adult tx's unique index can be quite short : blknum_txoffset. this in turn saves space elsewhere, for all time.
mircea_popescu: lubby coding. better than simple hashing for this purpose. deifnitely.
mircea_popescu: asciilifeform you know that's not a half bad idea
asciilifeform: quite the opposite.
asciilifeform: (and he cannot even begin to work on a block until he knows Z and goes, fetches the required old tx ! no other miner has any incentive to help him do this.)
asciilifeform: as far as i can see, this solves. Z depends on previous block, and the xor'd output is ~covered~ by the hash (and nonce) of the currently-worked-on block. so miner cannot craft his Z, he is forced to suck it up.
asciilifeform: ( Z from here-on in this gedankenexperiment is simply a value that determines which 3 -- if arity==3 -- old tx's get xor'd )
asciilifeform: .... another pill against 'waltzers' : Z depends on the ~previous~ block. ☟︎
asciilifeform: what is the complexity of actually fetching the Nth tx , if you can also make use of the T(...)xorT(...)xorT(...) in every block.
asciilifeform: and we have the luby transform above.
asciilifeform: suppose that tx's (recall, fixed width) position in the block, is also kept inside it. (e.g., tx # 100 will start with a 16bit field containing 0x0064 .)
asciilifeform: now challenge for the reader !
asciilifeform: (either this, or simply replace 'nonce' in the equation, with a Z, that is equal to a hash over the ~transactions in the candidate block~, considerably more painful to waltz than the nonce )
asciilifeform: what remains is to compute the minimal arity for the attack to be impractical. and prove said fact.
deedbot: http://trilema.com/2017/the-story-of-the-scared-slut/ << Trilema - The Story of the scared slut. ☟︎
asciilifeform: in above example, the 'arity' of the xor is 3. and mircea_popescu will probably answer, when he comes back , that evil miner will waltz the nonce until the 3 necessary tx are the ones that fit in his pocket. but arity doesn't have to be 3.
asciilifeform: theoretically it also means that a tx, as time goes to infinity, will have infinite number of confirmations...
asciilifeform: this also entirely annihilates the possibility that a future enemy could monkey with contents of old blocks by finding hash collisions.
asciilifeform: there is no way to practically compute this value without having a copy of the blockchain. and it also ends up being luby-transformable into any one of the 3 old tx if you have the other 2. a kind of perpetual redundancy in the storage . ☟︎
asciilifeform: T( nonce mod Tmax ) xor T ( H(nonce) mod Tmax ) xor T ( H(H(nonce)) mod Tmax ).
asciilifeform: say every new block , to be valid, must contain a tx-sized slot (not covered by the nonce hash, but see below) that is computed as follows:
asciilifeform: ooook try this on for size : suppose fixed-width TX (as discussed earlier.) T(N) is the Nth tx, T(0) is the first tx in genesis block, etc. Tmax is the last tx in the currentheightblock. ☟︎
asciilifeform goes into the pit, bbl.
mircea_popescu: if you ever get kicked out of engineering tower should prolly try out the arts, become draughtsman
asciilifeform: the one that blooms for a bit, and dies.
asciilifeform: or whatever that toy is called
mircea_popescu: but just because we're all going to die it does not follow we should go around on stilts and weird beak masks either
mircea_popescu: i have no argument with that.
asciilifeform: (for instance, can demand that the miner find a Q that depends only on the parts of the block he cannot easily spin.)
mircea_popescu: i dunno. the further you go prng-away from the "quote the nth line in the log", the closer you getr to "my solution to mining is mining+mining"
asciilifeform: open problem. betcha one can find the pill for this.,
mircea_popescu: cheaper to spin the nonces.
asciilifeform: the nonce is Q. miner has to now find an old block that , treated with the above walk, contains F(Q). and point to the block # and the requisite offset .
asciilifeform: the cheat -- works. say your hash is a keccak that eats 512b blocks and produces 512b block.
mircea_popescu: you can't turn out your wife without being married to a whore, alfie.
mircea_popescu: cuz it'll be == the hashing if it's as hard as the hashing.
asciilifeform: how's that
asciilifeform: in the same way.
asciilifeform: it can be made as painful as the hashing is to begin with
asciilifeform: (and even then may turn up short, and have to go back for a new nonce)
asciilifeform: depending on how you make F, he does need to examine all blocks.
mircea_popescu: why ? statistically, only to a fraction.
asciilifeform: but requires access to all old blocks, to search for.
asciilifeform: for sake of argument, an F, such that a substring S of old block B makes F(nonce + B) = true.
asciilifeform: say the miner has to find a string in an old block , as part of mining, that fits a nonce-derived pattern.
mircea_popescu: half the reason i'm a shitty scientist : unlike the good ones, i get laid.
asciilifeform: didn't mircea_popescu find a new chocolate icecream shop! he oughta go there, eat some, come back with theorem.
asciilifeform: this is an open problem, because 'miners don't need the blocks' is also imho intolerable.
asciilifeform: convergence to handful of massive google-like datacenters for ~nodes~ -- not miners, but also nodes -- is inherently usgistic imho.
mircea_popescu: asciilifeform there is that.
mircea_popescu: he who knows a secret key is a bitcoin user ; he who can say if ia signed transaction is valid or invalid is a bitcoin node ; he who can include a bitcoin transaction in a block is a bitcoin miner.
asciilifeform: (which is closer to O(NlogN)
asciilifeform: O(N^2) verification of each incoming block, is even worse of a 'heat death' rate than of traditional bitcoin
mircea_popescu: besides the point.
asciilifeform: that is to say, all sane people